From patchwork Fri Nov 3 12:35:19 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Bin Cheng X-Patchwork-Id: 833841 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-465837-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="yoZipxOW"; 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 3yT1kw73MJz9s7f for ; Fri, 3 Nov 2017 23:40:23 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:content-type:mime-version; q=dns; s=default; b=KgLFyC1XqNfc3xaODs2RgLTSAzNOKaWXFiRMnEnpaZOz+LRfut gZW4nRWh+JJi/y9L2Hq34Nz0M15KRKkzrajs0gSNKTtvE/nEs8bEPEzFaAFH8GJ/ Q4/ZobKI47x82TX2IrU9NRs/mAyHVVJJU6L1M31iaiGfXEkJSQ8xI06dE= 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:from :to:cc:subject:date:message-id:content-type:mime-version; s= default; bh=8ZrhNsKIfQzIWO/WhyOx/mYSCzg=; b=yoZipxOWmMfxuDJT+pff jQ5bbtQ36YO6abOituKFBYwUrBtdooGHBYuK6X1x83yuBUEOoXFfiZzyPsos6bZZ mClOHWo7g1JIXj2oEX2adYYX3aiFPFhv0zQSm2lV9MP0AWhrgNVBsXfaEv95fgI9 Xy3ygFAgSAILm4BqiMbn+WY= Received: (qmail 4836 invoked by alias); 3 Nov 2017 12:35:27 -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 4714 invoked by uid 89); 3 Nov 2017 12:35:26 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-25.9 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS, SPF_PASS autolearn=ham version=3.3.2 spammy=Hx-exchange-antispam-report-cfa-test:3231021, type_traits, 5310, exploit X-HELO: EUR01-DB5-obe.outbound.protection.outlook.com Received: from mail-db5eur01on0075.outbound.protection.outlook.com (HELO EUR01-DB5-obe.outbound.protection.outlook.com) (104.47.2.75) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 03 Nov 2017 12:35:24 +0000 Received: from DB5PR0801MB2742.eurprd08.prod.outlook.com (10.166.176.26) by DB5PR0801MB2742.eurprd08.prod.outlook.com (10.166.176.26) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256) id 15.20.197.13; Fri, 3 Nov 2017 12:35:20 +0000 Received: from DB5PR0801MB2742.eurprd08.prod.outlook.com ([10.166.176.26]) by DB5PR0801MB2742.eurprd08.prod.outlook.com ([10.166.176.26]) with mapi id 15.20.0197.013; Fri, 3 Nov 2017 12:35:20 +0000 From: Bin Cheng To: "gcc-patches@gcc.gnu.org" CC: nd Subject: [PATCH PR82776]Exploit more undefined pointer overflow behavior in loop niter analysis Date: Fri, 3 Nov 2017 12:35:19 +0000 Message-ID: authentication-results: spf=none (sender IP is ) smtp.mailfrom=Bin.Cheng@arm.com; x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1; DB5PR0801MB2742; 6:vBRiKZSFSiD3f7RDrDoPv3ei+ESHY6j5/OEEnYvHXNDhGZ3Fs0PZEzSsr9drU8872CPO6x/WogoCCDXOEqnFt2QcJzrAF2FEwwFmaZTNRJ75+aKmFButYVg6laZLHGNeMuvUWyDjk+GgKlnD59CkSTQhRTFitnawZQgTUu+yTj3bqM9Z1VMftbzBBVnr1fqL7gGzmRjVqazX7e0DeS3XdOjoHiF5Ii8vRSxX4RxudvTclYxwjMS1ayhEqfXjqsT0KrHx4Vy/we9Qkh3y6xVXZxv/N5jzMeSfrFU42mTUUBVMF+Y882sgaI3adQgsxbRDJGpng+sRkIe6Sl5grwIWWyDUK2dJGIvhWkRxpW0JRmE=; 5:2Zw94OkQLCyVI8y4BE1K2UmaOupqa4p+xoxjfflRrzFy6fP6F5H/zh1+nvrSlmfvC/UcGr2EDSV8eqXu0Fm72LsxoE9n1dgs9ZmCORHHFel2+oTceLdJoFYqywNENGXLcj0+QIYlNegfS5aaTiD1BcLeQszmiRWMU3YbB7EIlsA=; 24:wy0KAVPRutZTSdiQN0+RPdDFnUWLnpa18jVtE5qnafIotGnVpkTb6bBMMST6Cy8wDoROoFvMGHKMs5lTdA5TyT0aug0GaMQEq4f3U8HaygA=; 7:DndHnqdRGxpTx84e5c9IrCtF72tSzn45WBLp2hHY9DfMae6GJi/M2fa4VVxMO5KPHkUJTzP2QMJNpao0W2iGFsNEFdrpMKsIUiOgdXgFsKinMiLTrFymvoIC9T9X1ESEyTmN09JumkuWWqiXVE7X/KPHcOQnfrKZ8PAKk6x3ifMjmp2i+L244PYsfT2M2AyWES2fAStUjultJAtyBXlOdXzJiPaNE1zSHLngZgz7esDy5jAVD/X6BekReLnh5hm3 x-ms-exchange-antispam-srfa-diagnostics: SSOS; x-ms-office365-filtering-correlation-id: 22b827c6-d1b8-44dc-5d7f-08d522b7586e x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001)(4534020)(4602075)(4627115)(201703031133081)(201702281549075)(48565401081)(2017052603199)(49563074); SRVR:DB5PR0801MB2742; x-ms-traffictypediagnostic: DB5PR0801MB2742: nodisclaimer: True x-exchange-antispam-report-test: UriScan:(180628864354917); x-microsoft-antispam-prvs: x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(100000700101)(100105000095)(100000701101)(100105300095)(100000702101)(100105100095)(102415395)(6040450)(2401047)(8121501046)(5005006)(10201501046)(3002001)(3231021)(100000703101)(100105400095)(93006095)(93001095)(6055026)(6041248)(20161123558100)(201703131423075)(201702281528075)(201703061421075)(201703061406153)(20161123560025)(20161123564025)(20161123555025)(20161123562025)(6072148)(201708071742011)(100000704101)(100105200095)(100000705101)(100105500095); SRVR:DB5PR0801MB2742; BCL:0; PCL:0; RULEID:(100000800101)(100110000095)(100000801101)(100110300095)(100000802101)(100110100095)(100000803101)(100110400095)(100000804101)(100110200095)(100000805101)(100110500095); SRVR:DB5PR0801MB2742; x-forefront-prvs: 0480A51D4A x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(6009001)(346002)(376002)(39860400002)(377424004)(199003)(189002)(3280700002)(6916009)(6436002)(101416001)(4326008)(305945005)(3660700001)(2906002)(14454004)(81156014)(102836003)(6116002)(3846002)(81166006)(8936002)(8676002)(189998001)(6506006)(72206003)(5640700003)(77096006)(7696004)(5660300001)(74316002)(478600001)(7736002)(50986999)(2501003)(2351001)(53936002)(55016002)(54356999)(99936001)(105586002)(316002)(99286004)(106356001)(2900100001)(97736004)(9686003)(66066001)(68736007)(33656002)(25786009)(86362001); DIR:OUT; SFP:1101; SCL:1; SRVR:DB5PR0801MB2742; H:DB5PR0801MB2742.eurprd08.prod.outlook.com; FPR:; SPF:None; PTR:InfoNoRecords; A:1; MX:1; LANG:en; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-Network-Message-Id: 22b827c6-d1b8-44dc-5d7f-08d522b7586e X-MS-Exchange-CrossTenant-originalarrivaltime: 03 Nov 2017 12:35:19.9530 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: DB5PR0801MB2742 X-IsSubscribed: yes Hi, This is a simple patch exploiting more undefined pointer overflow behavior in loop niter analysis. Originally, it only supports POINTER_PLUS_EXPR if the offset part is IV. This patch also handles the case if pointer is IV. With this patch, the while(true) loop in test can be removed by cddce pass now. Bootstrap and test on x86_64 and AArch64. This patch introduces two failures: FAIL: g++.dg/pr79095-1.C -std=gnu++98 (test for excess errors) FAIL: g++.dg/pr79095-2.C -std=gnu++11 (test for excess errors) I believe this exposes inaccurate value range information issue. For below code: /* { dg-do compile } */ /* { dg-options "-Wall -O3" } */ typedef long unsigned int size_t; inline void fill (int *p, size_t n, int) { while (n--) *p++ = 0; } struct B { int* p0, *p1, *p2; size_t size () const { return size_t (p1 - p0); } void resize (size_t n) { if (n > size()) append (n - size()); } void append (size_t n) { if (size_t (p2 - p1) >= n) { fill (p1, n, 0); } } }; void foo (B &b) { if (b.size () != 0) b.resize (b.size () - 1); } GCC gives below warning with this patch: pr79095-1.C: In function ‘void foo(B&)’: pr79095-1.C:10:7: warning: iteration 4611686018427387903 invokes undefined behavior [-Waggressive-loop-optimizations] *p++ = 0; ~^~ pr79095-1.C:9:11: note: within this loop while (n--) ^~ Problem is VRP should understand that it's never the case with condition: (size_t (p2 - p1) >= n) in function B::append. So, any comment? Thanks, bin 2017-11-02 Bin Cheng PR tree-optimization/82776 * tree-ssa-loop-niter.c (infer_loop_bounds_from_pointer_arith): Handle POINTER_PLUS_EXPR in which the pointer is an IV. (infer_loop_bounds_from_signedness): Refine comment. gcc/testsuite 2017-11-02 Bin Cheng PR tree-optimization/82776 * g++.dg/pr82776.C: New test. * gcc.dg/tree-ssa/split-path-6.c: Refine test. diff --git a/gcc/testsuite/g++.dg/pr82776.C b/gcc/testsuite/g++.dg/pr82776.C new file mode 100644 index 0000000..2a66817 --- /dev/null +++ b/gcc/testsuite/g++.dg/pr82776.C @@ -0,0 +1,78 @@ +// PR tree-optimization/82776 +// { dg-do compile } +// { dg-options "-O2 -std=c++14 -fdump-tree-cddce2-details" } + +#include +#include +#include +#include +#include +#include + + +unsigned baz (unsigned); + +struct Chunk { + std::array tags_; + uint8_t control_; + + bool eof() const { + return (control_ & 1) != 0; + } + + static constexpr unsigned kFullMask = (1 << 14) - 1; + + unsigned occupiedMask() const { + return baz (kFullMask); + } +}; + +#define LIKELY(x) __builtin_expect((x), true) +#define UNLIKELY(x) __builtin_expect((x), false) + +struct Iter { + Chunk* chunk_; + std::size_t index_; + + void advance() { + // common case is packed entries + while (index_ > 0) { + --index_; + if (LIKELY(chunk_->tags_[index_] != 0)) { + return; + } + } + + // bar only skips the work of advance() if this loop can + // be guaranteed to terminate +#ifdef ENABLE_FORLOOP + for (std::size_t i = 1; i != 0; ++i) { +#else + while (true) { +#endif + // exhausted the current chunk + if (chunk_->eof()) { + chunk_ = nullptr; + break; + } + ++chunk_; + auto m = chunk_->occupiedMask(); + if (m != 0) { + index_ = 31 - __builtin_clz(m); + break; + } + } + } +}; + +static Iter foo(Iter iter) { + puts("hello"); + iter.advance(); + return iter; +} + +void bar(Iter iter) { + foo(iter); +} + +// { dg-final { scan-tree-dump-not "can not prove finiteness of loop" "cddce2" } } diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c b/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c index 682166f..2206d05 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-6.c @@ -53,10 +53,11 @@ oof () } void -lookharder (string) +lookharder (string, res) char *string; + char *res; { - register char *g; + register char *g = res; register char *s; for (s = string; *s != '\0'; s++) { diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index 6efe67a..7c1ac61 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -3422,7 +3422,7 @@ static void infer_loop_bounds_from_pointer_arith (struct loop *loop, gimple *stmt) { tree def, base, step, scev, type, low, high; - tree var, ptr; + tree rhs2, rhs1; if (!is_gimple_assign (stmt) || gimple_assign_rhs_code (stmt) != POINTER_PLUS_EXPR) @@ -3436,12 +3436,13 @@ infer_loop_bounds_from_pointer_arith (struct loop *loop, gimple *stmt) if (!nowrap_type_p (type)) return; - ptr = gimple_assign_rhs1 (stmt); - if (!expr_invariant_in_loop_p (loop, ptr)) + rhs2 = gimple_assign_rhs2 (stmt); + if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (rhs2))) return; - var = gimple_assign_rhs2 (stmt); - if (TYPE_PRECISION (type) != TYPE_PRECISION (TREE_TYPE (var))) + rhs1 = gimple_assign_rhs1 (stmt); + if (!expr_invariant_in_loop_p (loop, rhs1) + && !expr_invariant_in_loop_p (loop, rhs2)) return; struct loop *uloop = loop_containing_stmt (stmt); @@ -3521,6 +3522,8 @@ infer_loop_bounds_from_signedness (struct loop *loop, gimple *stmt) allocated size, - signed variables should not overflow when flag_wrapv is not set. + + - pointer variables should not overflow when flag_wrapv is not set. */ static void