From patchwork Mon May 13 23:40:25 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Marc Glisse X-Patchwork-Id: 1099141 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-500599-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=none (p=none dis=none) header.from=inria.fr Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="RZ1RZ+o1"; dkim-atps=neutral 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 452y4M5xJrz9sBV for ; Tue, 14 May 2019 09:40:44 +1000 (AEST) 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:in-reply-to:message-id:references:mime-version :content-type; q=dns; s=default; b=P3wEaW5jSm3/RZ70/o46aPT4yJJX8 f7iC98SX+E7YJK5bGZShC6lODSEkuGXOrBTSKhDSwwSJAVTGWDgfK1BLQh+U22dN 5UGiMmsxXcR0w7YYzV7n4ILI8jlCjGxqQCUUGcP66LXGLH8KN7bZpSmhaVc5u7yu YOmyO2cKxQN8Ss= 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:in-reply-to:message-id:references:mime-version :content-type; s=default; bh=cTZn8MDUjkNwpsCRnEGy5dU68po=; b=RZ1 RZ+o12j/ReISXvD9xkz0gY6ko3Ag5HgID2bxvFfNmTT2VsYpeB2HdRIPqBVj1K1a lcPxGYi0iexsQuU9GwOFjzWhbKsE5OBq/CsU7OwLUFX3AdC3m+XsZO9hNxaqbIUx aABLS0ry7WcyvhrGSlIQqyuZ+7I/8oH4wTld559Q= Received: (qmail 86480 invoked by alias); 13 May 2019 23:40:37 -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 86472 invoked by uid 89); 13 May 2019 23:40:36 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-7.4 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, SPF_PASS autolearn=ham version=3.3.1 spammy=weaker, H*c:HHHHHHH, shortcut, *s2 X-HELO: mail3-relais-sop.national.inria.fr Received: from mail3-relais-sop.national.inria.fr (HELO mail3-relais-sop.national.inria.fr) (192.134.164.104) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 13 May 2019 23:40:34 +0000 Received: from grove.saclay.inria.fr ([193.55.177.244]) by mail3-relais-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 14 May 2019 01:40:32 +0200 Date: Tue, 14 May 2019 01:40:25 +0200 (CEST) From: Marc Glisse To: gcc-patches@gcc.gnu.org Subject: [V2] malloc cannot alias preexisting pointers In-Reply-To: Message-ID: References: User-Agent: Alpine 2.02 (DEB 1266 2009-07-14) MIME-Version: 1.0 Here is a version of the patch with a cheaper test, and an extra testcase for Martin. (I kept the tree-ssa-loop-niter.c part although I am not using it anymore) 2019-05-15 Marc Glisse gcc/ * tree-ssa-loop-niter.c (stmt_dominates_stmt_p): Handle NULL basic block. * tree-ssa-alias.c (quick_stmt_dominates_stmt_p): New function. (ptr_derefs_may_alias_p): Detect malloc and an older pointer. gcc/testsuite/ * g++.dg/tree-ssa/ldist-2.C: New file. * gcc.dg/alias-17.c: New file. Index: gcc/testsuite/g++.dg/tree-ssa/ldist-2.C =================================================================== --- gcc/testsuite/g++.dg/tree-ssa/ldist-2.C (nonexistent) +++ gcc/testsuite/g++.dg/tree-ssa/ldist-2.C (working copy) @@ -0,0 +1,14 @@ +// { dg-do compile { target c++11 } } +// { dg-options "-O3 -fdump-tree-optimized" } + +#include +#include +#include +// Remove those 2 inlines once gcc knows that new/delete are special +inline void* operator new(std::size_t n){return malloc(n);} +inline void operator delete(void*p){free(p);} +typedef std::unique_ptr T; +typedef std::vector V; +void f(V&v){v.reserve(1024);} + +/* { dg-final { scan-tree-dump "memcpy" "optimized" } } */ Index: gcc/testsuite/gcc.dg/alias-17.c =================================================================== --- gcc/testsuite/gcc.dg/alias-17.c (nonexistent) +++ gcc/testsuite/gcc.dg/alias-17.c (working copy) @@ -0,0 +1,16 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +__attribute__((malloc)) void*mymalloc(void); +int g; +int*f(int**p){ + int*q=*p; + if(!q)return 0; // new basic block, because the optimization is weak + int*r=mymalloc(); + *q=1; + *r=2; + g=*q; + return r; +} + +/* { dg-final { scan-tree-dump "g = 1;" "optimized"} } */ Index: gcc/tree-ssa-alias.c =================================================================== --- gcc/tree-ssa-alias.c (revision 271135) +++ gcc/tree-ssa-alias.c (working copy) @@ -118,20 +118,42 @@ dump_alias_stats (FILE *s) + alias_stats.ref_maybe_used_by_call_p_may_alias); fprintf (s, " call_may_clobber_ref_p: " HOST_WIDE_INT_PRINT_DEC" disambiguations, " HOST_WIDE_INT_PRINT_DEC" queries\n", alias_stats.call_may_clobber_ref_p_no_alias, alias_stats.call_may_clobber_ref_p_no_alias + alias_stats.call_may_clobber_ref_p_may_alias); dump_alias_stats_in_alias_c (s); } +/* A faster, weaker version of stmt_dominates_stmt_p. */ + +static bool +quick_stmt_dominates_stmt_p (gimple *s1, gimple *s2) +{ + basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2); + + if (!bb1 + || s1 == s2) + return true; + + if (!bb2) + return false; + + if (bb1 == bb2) + /* Punt. Except in a few passes that maintain UIDs, the only way to answer + is to walk through statements, which is too expensive. */ + return false; + + return dominated_by_p (CDI_DOMINATORS, bb2, bb1); +} + /* Return true, if dereferencing PTR may alias with a global variable. */ bool ptr_deref_may_alias_global_p (tree ptr) { struct ptr_info_def *pi; /* If we end up with a pointer constant here that may point to global memory. */ @@ -284,20 +306,39 @@ ptr_derefs_may_alias_p (tree ptr1, tree || !POINTER_TYPE_P (TREE_TYPE (ptr1)) || !POINTER_TYPE_P (TREE_TYPE (ptr2))) return true; /* We may end up with two empty points-to solutions for two same pointers. In this case we still want to say both pointers alias, so shortcut that here. */ if (ptr1 == ptr2) return true; + /* Memory returned by malloc cannot alias with a pre-existing pointer. + This is extremely crude, the order between the statements may be quite + arbitrary. */ + if (in_gimple_form && dom_info_available_p (cfun, CDI_DOMINATORS)) + { + gimple *def1 = SSA_NAME_DEF_STMT (ptr1); + gimple *def2 = SSA_NAME_DEF_STMT (ptr2); + tree decl; + if ((is_gimple_call (def2) + && (decl = gimple_call_fndecl (def2)) + && DECL_IS_MALLOC (decl) + && quick_stmt_dominates_stmt_p (def1, def2)) + || (is_gimple_call (def1) + && (decl = gimple_call_fndecl (def1)) + && DECL_IS_MALLOC (decl) + && quick_stmt_dominates_stmt_p (def2, def1))) + return false; + } + /* If we do not have useful points-to information for either pointer we cannot disambiguate anything else. */ pi1 = SSA_NAME_PTR_INFO (ptr1); pi2 = SSA_NAME_PTR_INFO (ptr2); if (!pi1 || !pi2) return true; /* ??? This does not use TBAA to prune decls from the intersection that not both pointers may access. */ return pt_solutions_intersect (&pi1->pt, &pi2->pt); Index: gcc/tree-ssa-loop-niter.c =================================================================== --- gcc/tree-ssa-loop-niter.c (revision 271135) +++ gcc/tree-ssa-loop-niter.c (working copy) @@ -4433,20 +4433,23 @@ stmt_dominates_stmt_p (gimple *s1, gimpl if (gimple_code (s1) == GIMPLE_PHI) return true; for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi)) if (gsi_stmt (bsi) == s1) return true; return false; } + if (!bb2) + return false; + return dominated_by_p (CDI_DOMINATORS, bb2, bb1); } /* Returns true when we can prove that the number of executions of STMT in the loop is at most NITER, according to the bound on the number of executions of the statement NITER_BOUND->stmt recorded in NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT. ??? This code can become quite a CPU hog - we can have many bounds, and large basic block forcing stmt_dominates_stmt_p to be queried