From patchwork Fri Jan 27 11:20:36 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aldy Hernandez X-Patchwork-Id: 720631 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 3v8xDc2NdBz9t1P for ; Fri, 27 Jan 2017 22:21:02 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="myXuSBp6"; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :subject:to:references:cc:from:message-id:date:mime-version :in-reply-to:content-type; q=dns; s=default; b=llx9rVqoQxcZlTQxG RKdGp9uAbis3LJIMwvDe6qjsf/b+GGr73yqq+CdHW1aKkOyK1WptNNUVokSXRpyt EF7EBodhyhYqlCf1J1NIm7nr9cBjhqkPvCM4/foYty4sXKY0o/WWkL3Mp5n/wzOD 1EaROmkQ5weu4rwaACO0btIL9Q= 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 :subject:to:references:cc:from:message-id:date:mime-version :in-reply-to:content-type; s=default; bh=9QipbsqAPm4HZz84EqYw0rI yP30=; b=myXuSBp6fjWWmt1J57HYz2J+PDHRQ+/j6FDNo9rxHxLj84oXV5xS0qE U6nGnWHHCgJBpMQLdnwDTvzwyRQ5Qy/x6UFlTcbCnWXMW72lFqRR2POhqhUuvBhJ dAVaY2z40H17DlmmD6Ic73MGFtxNKCckPnRABTLVw2eMdWwROHqA= Received: (qmail 852 invoked by alias); 27 Jan 2017 11:20:53 -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 827 invoked by uid 89); 27 Jan 2017 11:20:52 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-5.1 required=5.0 tests=BAYES_00, RP_MATCHES_RCVD, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=H*f:sk:dcb995e, bitmap_iterator, tree-ssa.h, UD:backend.h X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 27 Jan 2017 11:20:42 +0000 Received: from int-mx09.intmail.prod.int.phx2.redhat.com (int-mx09.intmail.prod.int.phx2.redhat.com [10.5.11.22]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id DC5A1C05B1C4; Fri, 27 Jan 2017 11:20:41 +0000 (UTC) Received: from abulafia.quesejoda.com (ovpn-117-20.ams2.redhat.com [10.36.117.20]) by int-mx09.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id v0RBKb4K009458; Fri, 27 Jan 2017 06:20:38 -0500 Subject: Re: [PR tree-optimization/71691] Fix unswitching in presence of maybe-undef SSA_NAMEs (take 2) To: Richard Biener References: <5e79620e-8adb-7768-a34e-32fd286995f0@redhat.com> <1e426a06-270b-07fe-0e95-ef3382b614c2@redhat.com> <0ff3a68e-3e2c-c0df-8c48-b02dac40d621@redhat.com> <39c1ceff-5584-210c-6ebc-12e8d234cffb@redhat.com> Cc: gcc-patches , Jeff Law From: Aldy Hernandez Message-ID: <50a9aa36-16ff-49f0-59fb-9bb08733b94a@redhat.com> Date: Fri, 27 Jan 2017 06:20:36 -0500 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.6.0 MIME-Version: 1.0 In-Reply-To: On 01/26/2017 07:29 AM, Richard Biener wrote: > On Thu, Jan 26, 2017 at 1:04 PM, Aldy Hernandez wrote: >> On 01/24/2017 07:23 AM, Richard Biener wrote: > Your initial on-demand approach is fine to catch some of the cases but it > will not handle those for which we'd need post-dominance. > > I guess we can incrementally add that. No complaints from me. This is my initial on-demand approach, with a few fixes you've commented on throughout. As you can see, there is still an #if 0 wrt to using your suggested conservative handling of memory loads, which I'm not entirely convinced of, as it pessimizes gcc.dg/loop-unswitch-1.c. If you feel strongly about it, I can enable the code again. Also, I enhanced gcc.dg/loop-unswitch-1.c to verify that we're actually unswitching something. It seems kinda silly that we have various unswitch tests, but we don't actually check whether we have unswitched anything. This test was the only one in the *unswitch*.c set that I saw was actually being unswitched. Of course, if you don't agree with my #if 0 above, I will remove this change to the test. Finally, are we even guaranteed to unswitch in loop-unswitch-1.c across architectures? If not, again, I can remove the one-liner. How does this look for trunk? Aldy gcc/ PR tree-optimization/71691 * bitmap.h (class auto_bitmap): New. * tree-ssa-defined-or-undefined.c: New file. * tree-ssa-defined-or-undefined.h: New file. * Makefile.in (tree-ssa-defined-or-undefined.o): New. * tree-ssa-loop-unswitch.c (tree_may_unswitch_on): Add defined_or_undefined parameter. Use defined_or_undefined instead of ssa_undefined_value_p. (tree_unswitch_single_loop): Instantiate defined_or_undefined variable. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 821584a..e0de276 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1507,6 +1507,7 @@ OBJS = \ tree-ssa-coalesce.o \ tree-ssa-copy.o \ tree-ssa-dce.o \ + tree-ssa-defined-or-undefined.o \ tree-ssa-dom.o \ tree-ssa-dse.o \ tree-ssa-forwprop.o \ diff --git a/gcc/bitmap.h b/gcc/bitmap.h index 196738b..f158b44 100644 --- a/gcc/bitmap.h +++ b/gcc/bitmap.h @@ -802,4 +802,25 @@ bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no) bmp_iter_and_compl (&(ITER), &(BITNUM)); \ bmp_iter_next (&(ITER), &(BITNUM))) +/* A class that ties the lifetime of a bitmap to its scope. */ +class auto_bitmap +{ + public: + auto_bitmap () { bits = BITMAP_ALLOC (NULL); } + ~auto_bitmap () { BITMAP_FREE (bits); } + // Allow calling bitmap functions on our bitmap. + operator bitmap () { return bits; } + + private: + // Prevent making a copy that references our bitmap. + auto_bitmap (const auto_bitmap &); + auto_bitmap &operator = (const auto_bitmap &); +#if __cplusplus >= 201103L + auto_bitmap (auto_bitmap &&); + auto_bitmap &operator = (auto_bitmap &&); +#endif + + bitmap bits; +}; + #endif /* GCC_BITMAP_H */ diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-1.c b/gcc/testsuite/gcc.dg/loop-unswitch-1.c index 930364c..f6fc41d 100644 --- a/gcc/testsuite/gcc.dg/loop-unswitch-1.c +++ b/gcc/testsuite/gcc.dg/loop-unswitch-1.c @@ -1,6 +1,6 @@ /* For PR rtl-optimization/27735 */ /* { dg-do compile } */ -/* { dg-options "-O2 -funswitch-loops" } */ +/* { dg-options "-O2 -funswitch-loops -fdump-tree-unswitch-details" } */ void set_color(void); void xml_colorize_line(unsigned int *p, int state) @@ -32,3 +32,5 @@ parse_tag: ; } } +/* Test that we actually unswitched something. */ +/* { dg-final { scan-tree-dump ";; Unswitching loop" "unswitch" } } */ diff --git a/gcc/testsuite/gcc.dg/loop-unswitch-5.c b/gcc/testsuite/gcc.dg/loop-unswitch-5.c new file mode 100644 index 0000000..b41e853 --- /dev/null +++ b/gcc/testsuite/gcc.dg/loop-unswitch-5.c @@ -0,0 +1,51 @@ +/* PR middle-end/71691 */ +/* { dg-do run } */ +/* { dg-options "-fno-tree-vrp -O2 -funswitch-loops -fdump-tree-unswitch-details" } */ + +/* Note: The -fno-tree-vrp above is only there to avoid VRP papering + over the problem. */ + +char b; +short f; +unsigned e; +int g = 20; + +void +foo () +{ + int l, h; + for (l = 0; l <= 7; l++) + { + int j = 38; + if (g) + h = 0; + for (; h <= 7; h++) + { + int i, k = b % (j % 4); + g = f; + for (;;) + { + j = 6 || b; + if (e) + { + for (; j; --j) + if (k) + __builtin_printf ("%d", 9); + if (i) + __builtin_printf ("%d", j); + } + if (l) + continue; + break; + } + i = f || b; + } + } +} + +int +main () +{ + foo (); + return 0; +} diff --git a/gcc/tree-ssa-defined-or-undefined.c b/gcc/tree-ssa-defined-or-undefined.c new file mode 100644 index 0000000..0ee91e5 --- /dev/null +++ b/gcc/tree-ssa-defined-or-undefined.c @@ -0,0 +1,118 @@ +/* Simple class for classifying SSA_NAMEs that are either fully + defined or possibly undefined. + + This is meant to support conservative analysis for optimization + purposes, not for generating warnings. The analysis for generating + warnings is deeper to avoid generation of false positives. + + Copyright (C) 2017 Free Software Foundation, Inc. + Contributed by Aldy Hernandez . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple.h" +#include "ssa.h" +#include "tree-ssa.h" +#include "cfgloop.h" +#include "tree-ssa-defined-or-undefined.h" + +/* Return TRUE if an SSA_NAME maybe undefined. */ + +bool +defined_or_undefined::is_maybe_undefined (const tree name) +{ + auto_bitmap visited_ssa; + auto_vec worklist; + worklist.safe_push (name); + bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (name)); + while (!worklist.is_empty ()) + { + tree t = worklist.pop (); + + /* If it's obviously undefined, avoid further computations. */ + if (ssa_undefined_value_p (t, true)) + return true; + + /* A PARM_DECL will not have an SSA_NAME_DEF_STMT. Parameters + get their initial value from function entry. */ + if (SSA_NAME_VAR (t) && TREE_CODE (SSA_NAME_VAR (t)) == PARM_DECL) + return false; + + gimple *def = SSA_NAME_DEF_STMT (t); + + /* Check that all the PHI args are fully defined. */ + if (gphi *phi = dyn_cast (def)) + { + if (virtual_operand_p (PHI_RESULT (phi))) + continue; + for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i) + { + tree t = gimple_phi_arg_def (phi, i); + /* If an SSA has already been seen, it may be a loop, + but we can continue and ignore this use. Otherwise, + add the SSA_NAME to the queue and visit it later. */ + if (TREE_CODE (t) == SSA_NAME + && bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t))) + worklist.safe_push (t); + } + continue; + } + + /* Handle calls and memory loads conservatively. */ + if (!is_gimple_assign (def) +#if 0 + /* + This will inhibit unswitching in the presence of memory loads, + which causes gcc.dg/loop_unswitch-1.c to FAIL because we no longer + unswitch: + + for (;;) { + c = *p; + ... + if (c) + stuff; + else + other_stuff; + } + */ + || (gimple_assign_single_p (def) + && gimple_vuse (def))) +#endif + ) + return true; + + /* Check that any SSA names used to define NAME are also fully + defined. */ + use_operand_p use_p; + ssa_op_iter iter; + FOR_EACH_SSA_USE_OPERAND (use_p, def, iter, SSA_OP_USE) + { + tree t = USE_FROM_PTR (use_p); + /* If an SSA has already been seen, it may be a loop, + but we can continue and ignore this use. Otherwise, + add the SSA_NAME to the queue and visit it later. */ + if (bitmap_set_bit (visited_ssa, SSA_NAME_VERSION (t))) + worklist.safe_push (t); + } + } + return false; +} diff --git a/gcc/tree-ssa-defined-or-undefined.h b/gcc/tree-ssa-defined-or-undefined.h new file mode 100644 index 0000000..aef0908 --- /dev/null +++ b/gcc/tree-ssa-defined-or-undefined.h @@ -0,0 +1,59 @@ +/* Simple class for identifying SSA_NAMEs that are either fully defined + or maybe undefined. + + Copyright (C) 2017 Free Software Foundation, Inc. + Contributed by Aldy Hernandez . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#ifndef GCC_TREE_SSA_DEFINED_OR_UNDEFINED_H +#define GCC_TREE_SSA_DEFINED_OR_UNDEFINED_H + +/* Simple class for identifying SSA_NAMEs that are either fully + defined or maybe undefined. + + This is meant to support conservative analysis for optimization + purposes, not for generating warnings. The analysis for generating + warnings is deeper to avoid generation of false positives. + + Instantiation of this class triggers analysis which is not kept + up-to-date as changes in the IL or CFG are made. + + Queries will return the conservative result (maybe undefined) for + SSA_NAMEs that were not encountered during the initial + analysis. */ + +class defined_or_undefined +{ + private: + // Entry block of the current loop. + basic_block loop_entry; + vec loop_region; + public: + defined_or_undefined (struct loop *loop) + { loop_entry = loop->header; } + /* Note: We could implement a variant of this class that does not + need loop info. Until such need arises, leave this + unimplemented. */ + defined_or_undefined (); + // Return TRUE if SSA is maybe undefined. + bool is_maybe_undefined (tree ssa); + // Return TRUE if SSA is definitely defined. + bool is_defined (tree ssa) { return !is_maybe_undefined (ssa); } +}; + +#endif // GCC_TREE_SSA_DEFINED_OR_UNDEFINED_H diff --git a/gcc/tree-ssa-loop-unswitch.c b/gcc/tree-ssa-loop-unswitch.c index 92599fb..4452373 100644 --- a/gcc/tree-ssa-loop-unswitch.c +++ b/gcc/tree-ssa-loop-unswitch.c @@ -38,6 +38,7 @@ along with GCC; see the file COPYING3. If not see #include "gimple-iterator.h" #include "cfghooks.h" #include "tree-ssa-loop-manip.h" +#include "tree-ssa-defined-or-undefined.h" /* This file implements the loop unswitching, i.e. transformation of loops like @@ -77,7 +78,8 @@ along with GCC; see the file COPYING3. If not see static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree); static bool tree_unswitch_single_loop (struct loop *, int); -static tree tree_may_unswitch_on (basic_block, struct loop *); +static tree tree_may_unswitch_on (basic_block, struct loop *, + defined_or_undefined *); static bool tree_unswitch_outer_loop (struct loop *); static edge find_loop_guard (struct loop *); static bool empty_bb_without_guard_p (struct loop *, basic_block); @@ -113,7 +115,8 @@ tree_ssa_unswitch_loops (void) basic blocks (for what it means see comments below). */ static tree -tree_may_unswitch_on (basic_block bb, struct loop *loop) +tree_may_unswitch_on (basic_block bb, struct loop *loop, + defined_or_undefined *defined_or_undefined) { gimple *last, *def; gcond *stmt; @@ -138,7 +141,7 @@ tree_may_unswitch_on (basic_block bb, struct loop *loop) { /* Unswitching on undefined values would introduce undefined behavior that the original program might never exercise. */ - if (ssa_undefined_value_p (use, true)) + if (defined_or_undefined->is_maybe_undefined (use)) return NULL_TREE; def = SSA_NAME_DEF_STMT (use); def_bb = gimple_bb (def); @@ -200,6 +203,7 @@ tree_unswitch_single_loop (struct loop *loop, int num) gimple *stmt; bool changed = false; HOST_WIDE_INT iterations; + defined_or_undefined defined_or_undefined (loop); /* Perform initial tests if unswitch is eligible. */ if (num == 0) @@ -243,7 +247,7 @@ tree_unswitch_single_loop (struct loop *loop, int num) { /* Find a bb to unswitch on. */ for (; i < loop->num_nodes; i++) - if ((cond = tree_may_unswitch_on (bbs[i], loop))) + if ((cond = tree_may_unswitch_on (bbs[i], loop, &defined_or_undefined))) break; if (i == loop->num_nodes) @@ -363,7 +367,8 @@ tree_unswitch_single_loop (struct loop *loop, int num) /* Find a bb to unswitch on. */ for (; found < loop->num_nodes; found++) if ((bbs[found]->flags & BB_REACHABLE) - && (cond = tree_may_unswitch_on (bbs[found], loop))) + && (cond = tree_may_unswitch_on (bbs[found], loop, + &defined_or_undefined))) break; if (found == loop->num_nodes)