From patchwork Wed Mar 13 18:14:36 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 227315 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 E84DF2C00A0 for ; Thu, 14 Mar 2013 05:15:12 +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=1363803313; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Received:Date:From:To:Cc:Subject:Message-ID:Reply-To: MIME-Version:Content-Type:Content-Disposition:User-Agent: Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:Sender:Delivered-To; bh=k8usExo25jxhdycxgQz4 ean7Cao=; b=H2EzglGlYwXslzaiKbOjjn6kby7Rlqd+YWns42Rcj1IVtN1oRTXW 86j7xp5D4evgpThDKLNaWe40B9pGlbSZhXzPlB5GuLXmv1oIYV1+9sPSJ2xpnj2G wtRyZg5Vt4UEC/GsfhjT7tip9KVo0eLOxJJd88CqxeNCPKK9zMQn/9I= 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:Received:Received:Received:Date:From:To:Cc:Subject:Message-ID:Reply-To:MIME-Version:Content-Type:Content-Disposition:User-Agent:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=DAFX0sFMUeiHg63p71WhiJvXGOTUS5aZJA16tM6P0Kds6L3KVaBLnhaGsSBxsQ w7W/CprruAScgkHFquJuHc83C+IhaOQb7BqpQlESX58M9sy5iuTzFBuxH1rHz0m3 z5WCPagsXGdg4qalWOtzdeH0PPp8Rign9FWKjkItqCjBg=; Received: (qmail 15986 invoked by alias); 13 Mar 2013 18:14:55 -0000 Received: (qmail 15969 invoked by uid 22791); 13 Mar 2013 18:14:52 -0000 X-SWARE-Spam-Status: No, hits=-7.4 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, KHOP_SPAMHAUS_DROP, RCVD_IN_DNSWL_HI, RCVD_IN_HOSTKARMA_W, RP_MATCHES_RCVD, SPF_HELO_PASS, TW_CF, TW_TM X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 13 Mar 2013 18:14:40 +0000 Received: from int-mx12.intmail.prod.int.phx2.redhat.com (int-mx12.intmail.prod.int.phx2.redhat.com [10.5.11.25]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id r2DIEdIm030065 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Wed, 13 Mar 2013 14:14:39 -0400 Received: from zalov.cz (vpn1-7-228.ams2.redhat.com [10.36.7.228]) by int-mx12.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id r2DIEbNu002315 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Wed, 13 Mar 2013 14:14:39 -0400 Received: from zalov.cz (localhost [127.0.0.1]) by zalov.cz (8.14.5/8.14.5) with ESMTP id r2DIEb0E027967; Wed, 13 Mar 2013 19:14:37 +0100 Received: (from jakub@localhost) by zalov.cz (8.14.5/8.14.5/Submit) id r2DIEaQO027966; Wed, 13 Mar 2013 19:14:36 +0100 Date: Wed, 13 Mar 2013 19:14:36 +0100 From: Jakub Jelinek To: Richard Biener Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] Introduce -Waggressive-loop-optimizations (PR tree-optimization/53265) Message-ID: <20130313181436.GV12913@tucnak.redhat.com> Reply-To: Jakub Jelinek MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.21 (2010-09-15) 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! This patch is an attempt to warn about undefined behavior in simple loops with known constant number of latch executions, which probably is the most common case where gcc 4.8 started to turn finite loops involving undefined behavior before reaching last iteration into endless loops. Of course the patch doesn't guarantee warning for all such mistakes, and for loops without known constant number of latch executions it is question on what exactly we should warn about. Honza has some prototype patch, perhaps that could be done if loop->warned_aggressive_loop_optimizations is still false. To avoid false positives in some cases (e.g. exp_ch7.adb during bootstrap), I had to start warning only later on (with the advantage that at that point loops are preserved and thus we can set flag in the loop structure whether we've warned already). I had to tweak a couple of testcases (pr49518.c clearly can result in undefined behavior conditionally, longbranch2.C also had obvious undefined behavior (I've verified that r80000 cc1plus generated exactly same size and insn type code with original and fixed testcase, the only thing that differed were immediates in some instructions due to different field sizes). In cunroll-10.c we no longer do anything as it had known constant number of latch executions, thus no undefined behavior discovery is performed. In libgcc, the DW_CFA_GNU_window_save handling code was hardcoding SPARC register window setup, but that is also undefined behavior on targets that have fewer than 32 DWARF_FRAME_REGISTERS. I've just shut it up there, after all DW_CFA_GNU_window_save is only ever used on SPARC anyway. I've bootstrapped/regtested the patch together with a debugging patch to show where the last hunk in estimate_numbers_of_iterations_loop actually changed anything. It happened in ../../gcc/ada/exp_ch7.adb:3540 (see the PR, in dead code), we'd need a copyprop pass with cfgcleanup before cunrolli to avoid that, then in {sse4_2,avx}-vpcmp{i,e}strm-{1,2}.c /usr/src/gcc/gcc/testsuite/gcc.target/i386/sse4_2-pcmpstr.h:339 (reduced testcase -O2: short t[8]; static inline void bar (int x, int y) { short s[8]; int i, d = (x & 1) == 0 ? 16 : 8; if (x & 0x40) for (i = 0; i < d; i++) if (d == 8) s[i] = (y & (1 << i)) ? -1 : 0; __builtin_memcpy (t, s, sizeof s); } void foo (int y) { bar (0x26, y); } ) - here number_of_latch_iterations returns 0, apparently because it finds out that the loop will be never executed. Then gcc.dg/torture/pr49518.c:11 (see above, ok) and gcc.dg/pr53265.c (expected, many). So, I think we're fine. Ok for 4.8? 2013-03-13 Jakub Jelinek PR tree-optimization/53265 * common.opt (Waggressive-loop-optimizations): New option. * tree-ssa-loop-niter.c: Include tree-pass.h. (do_warn_aggressive_loop_optimizations): New function. (record_estimate): Call it. Don't add !is_exit bounds to loop->bounds if number_of_latch_executions returned constant. (estimate_numbers_of_iterations_loop): Call number_of_latch_executions early. If number_of_latch_executions returned constant, set nb_iterations_upper_bound back to it. * cfgloop.h (struct loop): Add warned_aggressive_loop_optimizations field. * Makefile.in (tree-ssa-loop-niter.o): Depend on $(TREE_PASS_H). * doc/invoke.texi (-Wno-aggressive-loop-optimizations): Document. * gcc.dg/pr53265.c: New test. * gcc.dg/torture/pr49518.c: Add -Wno-aggressive-loop-optimizations to dg-options. * g++.dg/opt/longbranch2.C (EBCOTLut): Double sizes of a2 and a3 arrays. * gcc.dg/tree-ssa/cunroll-10.c (main): Rename to foo. Add argument n, use it as high bound instead of 4. * unwind-dw2.c (execute_cfa_program): Avoid -Waggressive-array-optimizations warnings for DW_CFA_GNU_window_save on targets with DWARF_FRAME_REGISTERS < 32. * testsuite/libmudflap.c/fail37-frag.c: Add optimization barrier. Jakub --- gcc/common.opt.jj 2013-03-12 09:59:34.692099982 +0100 +++ gcc/common.opt 2013-03-12 13:47:08.922161154 +0100 @@ -505,6 +505,10 @@ Waggregate-return Common Var(warn_aggregate_return) Warning Warn about returning structures, unions or arrays +Waggressive-loop-optimizations +Common Var(warn_aggressive_loop_optimizations) Init(1) Warning +Warn if a loop with constant number of iterations triggers undefined behavior + Warray-bounds Common Var(warn_array_bounds) Warning Warn if an array is accessed out of bounds --- gcc/tree-ssa-loop-niter.c.jj 2013-03-12 09:59:34.740099692 +0100 +++ gcc/tree-ssa-loop-niter.c 2013-03-13 11:19:02.100060913 +0100 @@ -37,6 +37,7 @@ along with GCC; see the file COPYING3. #include "flags.h" #include "diagnostic-core.h" #include "tree-inline.h" +#include "tree-pass.h" #define SWAP(X, Y) do { affine_iv *tmp = (X); (X) = (Y); (Y) = tmp; } while (0) @@ -2525,6 +2526,40 @@ record_niter_bound (struct loop *loop, d loop->nb_iterations_estimate = loop->nb_iterations_upper_bound; } +/* Emit a -Waggressive-loop-optimizations warning if needed. */ + +static void +do_warn_aggressive_loop_optimizations (struct loop *loop, + double_int i_bound, gimple stmt) +{ + /* Don't warn if the loop doesn't have known constant bound. */ + if (!loop->nb_iterations + || TREE_CODE (loop->nb_iterations) != INTEGER_CST + || !warn_aggressive_loop_optimizations + /* To avoid warning multiple times for the same loop, + only start warning when we preserve loops. */ + || (cfun->curr_properties & PROP_loops) == 0 + /* Only warn once per loop. */ + || loop->warned_aggressive_loop_optimizations + /* Only warn if undefined behavior gives us lower estimate than the + known constant bound. */ + || i_bound.ucmp (tree_to_double_int (loop->nb_iterations)) >= 0 + /* And undefined behavior happens unconditionally. */ + || !dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (stmt))) + return; + + edge e = single_exit (loop); + if (e == NULL) + return; + + gimple estmt = last_stmt (e->src); + warning_at (gimple_location (stmt), OPT_Waggressive_loop_optimizations, + "iteration %E invokes undefined behavior", + double_int_to_tree (TREE_TYPE (loop->nb_iterations), i_bound)); + inform (gimple_location (estmt), "containing loop"); + loop->warned_aggressive_loop_optimizations = true; +} + /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. IS_EXIT is true if the loop is exited immediately after STMT, and this exit is taken at last when the STMT is executed BOUND + 1 times. @@ -2560,8 +2595,12 @@ record_estimate (struct loop *loop, tree return; /* If we have a guaranteed upper bound, record it in the appropriate - list. */ - if (upper) + list, unless this is an !is_exit bound (i.e. undefined behavior in + at_stmt) in a loop with known constant number of iterations. */ + if (upper + && (is_exit + || loop->nb_iterations == NULL_TREE + || TREE_CODE (loop->nb_iterations) != INTEGER_CST)) { struct nb_iter_bound *elt = ggc_alloc_nb_iter_bound (); @@ -2591,6 +2630,8 @@ record_estimate (struct loop *loop, tree if (i_bound.ult (delta)) return; + if (upper && !is_exit) + do_warn_aggressive_loop_optimizations (loop, i_bound, at_stmt); record_niter_bound (loop, i_bound, realistic, upper); } @@ -3311,6 +3352,11 @@ estimate_numbers_of_iterations_loop (str /* Force estimate compuation but leave any existing upper bound in place. */ loop->any_estimate = false; + /* Ensure that loop->nb_iterations is computed if possible. If it turns out + to be constant, we avoid undefined behavior implied bounds and instead + diagnose those loops with -Waggressive-loop-optimizations. */ + number_of_latch_executions (loop); + exits = get_loop_exit_edges (loop); likely_exit = single_likely_exit (loop); FOR_EACH_VEC_ELT (exits, i, ex) @@ -3345,6 +3391,17 @@ estimate_numbers_of_iterations_loop (str bound = gcov_type_to_double_int (nit); record_niter_bound (loop, bound, true, false); } + + /* If we know the exact number of iterations of this loop, try to + not break code with undefined behavior by not recording smaller + maximum number of iterations. */ + if (loop->nb_iterations + && TREE_CODE (loop->nb_iterations) == INTEGER_CST) + { + loop->any_upper_bound = true; + loop->nb_iterations_upper_bound + = tree_to_double_int (loop->nb_iterations); + } } /* Sets NIT to the estimated number of executions of the latch of the --- gcc/cfgloop.h.jj 2013-03-12 09:59:34.677100070 +0100 +++ gcc/cfgloop.h 2013-03-12 13:47:08.919161106 +0100 @@ -159,6 +159,10 @@ struct GTY ((chain_next ("%h.next"))) lo /* True if the loop can be parallel. */ bool can_be_parallel; + /* True if -Waggressive-loop-optimizations warned about this loop + already. */ + bool warned_aggressive_loop_optimizations; + /* An integer estimation of the number of iterations. Estimate_state describes what is the state of the estimation. */ enum loop_estimation estimate_state; --- gcc/Makefile.in.jj 2013-03-12 09:59:34.988098249 +0100 +++ gcc/Makefile.in 2013-03-12 13:47:08.919161106 +0100 @@ -2446,7 +2446,7 @@ tree-ssa-loop-niter.o : tree-ssa-loop-ni $(SYSTEM_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) $(PARAMS_H) \ $(TREE_INLINE_H) $(DIAGNOSTIC_H) $(TM_H) coretypes.h dumpfile.h \ $(DIAGNOSTIC_CORE_H) $(FLAGS_H) $(TREE_DATA_REF_H) \ - $(BASIC_BLOCK_H) $(GGC_H) intl.h $(GIMPLE_PRETTY_PRINT_H) + $(BASIC_BLOCK_H) $(GGC_H) intl.h $(GIMPLE_PRETTY_PRINT_H) $(TREE_PASS_H) tree-ssa-loop-ivcanon.o : tree-ssa-loop-ivcanon.c $(TREE_FLOW_H) $(CONFIG_H) \ $(SYSTEM_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) $(PARAMS_H) \ $(TREE_INLINE_H) $(DIAGNOSTIC_H) $(TM_H) coretypes.h \ --- gcc/doc/invoke.texi.jj 2013-03-12 14:22:01.000000000 +0100 +++ gcc/doc/invoke.texi 2013-03-12 16:45:04.580807698 +0100 @@ -232,7 +232,8 @@ Objective-C and Objective-C++ Dialects}. @xref{Warning Options,,Options to Request or Suppress Warnings}. @gccoptlist{-fsyntax-only -fmax-errors=@var{n} -Wpedantic @gol -pedantic-errors @gol --w -Wextra -Wall -Waddress -Waggregate-return -Warray-bounds @gol +-w -Wextra -Wall -Waddress -Waggregate-return @gol +-Waggressive-loop-optimizations -Warray-bounds @gol -Wno-attributes -Wno-builtin-macro-redefined @gol -Wc++-compat -Wc++11-compat -Wcast-align -Wcast-qual @gol -Wchar-subscripts -Wclobbered -Wcomment @gol @@ -4423,6 +4424,12 @@ Warn if any functions that return struct called. (In languages where you can return an array, this also elicits a warning.) +@item -Wno-aggressive-loop-optimizations +@opindex Wno-aggressive-loop-optimizations +@opindex Waggressive-loop-optimizations +Warn if in a loop with constant number of iterations the compiler detects +undefined behavior in some statement during one or more of the iterations. + @item -Wno-attributes @opindex Wno-attributes @opindex Wattributes --- gcc/testsuite/gcc.dg/pr53265.c.jj 2013-03-12 13:47:08.922161154 +0100 +++ gcc/testsuite/gcc.dg/pr53265.c 2013-03-13 11:23:52.592338941 +0100 @@ -0,0 +1,156 @@ +/* PR tree-optimization/53265 */ +/* { dg-do compile } */ +/* { dg-options "-O2 -Wall" } */ + +void bar (void *); +int baz (int); + +void +fn1 (void) +{ + unsigned int a[128]; + int i; + + for (i = 0; i < 128; ++i) /* { dg-message "note: containing loop" } */ + a[i] = i * 0x02000001; /* { dg-warning "invokes undefined behavior" } */ + bar (a); +} + +void +fn2 (void) +{ + unsigned long long a[128]; + int i; + + for (i = 0; i < 128; i++) /* { dg-message "note: containing loop" } */ + a[i] = (i + 1LL) * 0x0123456789ABCDEFLL; /* { dg-warning "invokes undefined behavior" } */ + bar (a); +} + +void +fn3 (void) +{ + unsigned char a[16], b[16], c[16]; + int i; + + bar (b); + for (i = 0; i < (int) (sizeof (a) / sizeof (a[0])); i++) /* { dg-message "note: containing loop" } */ + { + c[i + 8] = b[i]; /* { dg-warning "invokes undefined behavior" } */ + a[i + 8] = b[i + 8]; + } + bar (a); + bar (c); +} + +void +fn4 (void) +{ + unsigned int *a[32], *o, i; + + bar (a); + for (i = 0; i <= sizeof (a) / sizeof (a[0]); i++) /* { dg-message "note: containing loop" "" { xfail *-*-* } } */ + { + o = a[i]; /* { dg-warning "invokes undefined behavior" "" { xfail *-*-* } } */ + bar (o); + } +} + +void +fn5 (void) +{ + unsigned short a[23940]; + unsigned int b[1140]; + int j; + + bar (b); + for (j = 0; j < 1140; j++) /* { dg-message "note: containing loop" } */ + a[23940 + j - 950] = b[j]; /* { dg-warning "invokes undefined behavior" } */ + bar (a); +} + +void +fn6 (void) +{ + double a[4][3], b[12]; + int i; + bar (b); + for (i = 0; i < 12; i++) /* { dg-message "note: containing loop" } */ + a[0][i] = b[i] / 10000.0; /* { dg-warning "invokes undefined behavior" } */ + bar (a); +} + +void +fn7 (void) +{ + int a[16], b, c; + bar (a); + for (b = a[c = 0]; c < 16; b = a[++c]) /* { dg-warning "invokes undefined behavior" "" { xfail *-*-* } } */ + baz (b); +} + +/* { dg-message "note: containing loop" "" { xfail *-*-* } 88 } */ + +const void *va, *vb, *vc, *vd, *ve; +const void *vf[4]; +void +fn8 (void) +{ + unsigned long i; + vf[0] = va; vf[1] = vb; vf[2] = vc; vf[3] = vd; + for (i = 0; i < (sizeof (vf) / sizeof (vf[0])); i++) + if (!vf[i]) + vf[i] = ve; +} + +int wa, wb[53][5], wc[53][5]; + +void +fn9 (void) +{ + int i, j, k; + for (i = 0; i < 53; i++) + for (j = 16 / (((wa & 1) != 0) ? 8 : 4); j > 0; j--) + { + int d = 1; + if (wb[i][j] == 0 || wc[i][1] != 0) + continue; + for (k = 0; k < j; k++) + if (wc[i + k][1]) + { + d = 0; + break; + } + if (!d) + continue; + wc[i][j] = baz (0); + } +} + +int xa[18]; + +void +fn10 (void) +{ + int i; + for (i = 16; i < 32; i++) /* { dg-message "note: containing loop" } */ + xa[i] = 26; /* { dg-warning "invokes undefined behavior" } */ +} + +__attribute__((noinline)) static void +fn11 (int x) +{ + int i = 1; + if (x > 1) + do + baz (i); + while (++i != x); /* { dg-bogus "invokes undefined behavior" } */ +} + +void +fn12 (void) +{ + fn11 (1); + fn11 (1); + fn11 (1); +} --- gcc/testsuite/gcc.dg/torture/pr49518.c (revision 196628) +++ gcc/testsuite/gcc.dg/torture/pr49518.c (working copy) @@ -1,4 +1,5 @@ /* { dg-do compile } */ +/* { dg-options "-Wno-aggressive-loop-optimizations" } */ int a, b; struct S { unsigned int s, t, u; } c, d = { 0, 1, 0 }; --- gcc/testsuite/g++.dg/opt/longbranch2.C.jj 2011-07-11 10:39:36.000000000 +0200 +++ gcc/testsuite/g++.dg/opt/longbranch2.C 2013-03-13 15:02:59.814892282 +0100 @@ -15,8 +15,8 @@ public: class EBCOTLut : public JKeeper { unsigned char a1[1<<8]; - unsigned char a2[1<<8]; - unsigned char a3[1<<8]; + unsigned char a2[1<<9]; + unsigned char a3[1<<9]; long a4[1<<9]; public: EBCOTLut(void); --- gcc/testsuite/gcc.dg/tree-ssa/cunroll-10.c.jj 2012-11-05 08:55:20.000000000 +0100 +++ gcc/testsuite/gcc.dg/tree-ssa/cunroll-10.c 2013-03-13 18:48:20.000000000 +0100 @@ -2,10 +2,11 @@ /* { dg-options "-O3 -Warray-bounds -fdump-tree-cunroll-details" } */ int a[3]; int b[4]; -main() +int +foo (int n) { int i; - for (i=0;i<4;i++) + for (i=0;iregs.reg[reg].how = REG_SAVED_OFFSET; - fs->regs.reg[reg].loc.offset = (reg - 16) * sizeof (void *); - } + if (DWARF_FRAME_REGISTERS >= 32) + for (reg = 16; reg < 32; ++reg) + { + fs->regs.reg[reg].how = REG_SAVED_OFFSET; + fs->regs.reg[reg].loc.offset = (reg - 16) * sizeof (void *); + } break; case DW_CFA_GNU_args_size: --- libmudflap/testsuite/libmudflap.c/fail37-frag.c.jj 2008-09-05 12:57:41.000000000 +0200 +++ libmudflap/testsuite/libmudflap.c/fail37-frag.c 2013-03-13 11:32:36.925228158 +0100 @@ -13,7 +13,11 @@ main () { int i; for (i = 0; i < 5; i++) - x.s[i].f = 0; + { + /* Optimization barrier. Prevent gcc from seeing the undefined behavior. */ + __asm ("" : "+r" (i)); + x.s[i].f = 0; + } exit (0); } /* { dg-output "mudflap violation 1.*" } */