From patchwork Mon Jan 11 16:11:11 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bin Cheng X-Patchwork-Id: 566021 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 45134140C02 for ; Tue, 12 Jan 2016 03:11:32 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=Ru4lTpga; 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:from :to:cc:subject:date:message-id:mime-version:content-type; q=dns; s=default; b=RekT3sH+VpTWxapMM6ekqXqTcoKPJCk2RxTne8ndojzVBGJkY4 FSbfV3sLckOEj27NhhxzAIi4hTuIXunkiLrM0+Nv1vc7pVcdeBKfCqtiWW+cDf2P yZdIRGyJPfwyVdyXSUqYrIvwYt9cKxdP+1v6/OMSZW9oO8NBzFRx6aKGU= 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:mime-version:content-type; s= default; bh=nuhyeF9B53yt4yFooG6N2KMwdVM=; b=Ru4lTpgafT0OCtxlo3d5 EnxKNndgSeM25Ztj5F7LdVDFMCyW62ML1qg3G5i7/wTRj0sS163qNuLJ9uA1Zxb1 ZlxUsRbP6JrYd8uvP3gBw7QgztrD0R9EU1iMtdcWKhpxSx7W4kYFLcvYADANp4yl 7uyA7Nmximn6LYJnUnieBfc= Received: (qmail 10204 invoked by alias); 11 Jan 2016 16:11:25 -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 10128 invoked by uid 89); 11 Jan 2016 16:11:23 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.8 required=5.0 tests=AWL, BAYES_00, SPF_PASS autolearn=ham version=3.3.2 spammy=analyzing, H*MI:eurprd08, H*RU:sk:mail-he, Hx-spam-relays-external:sk:mail-he X-HELO: eu-smtp-delivery-143.mimecast.com Received: from eu-smtp-delivery-143.mimecast.com (HELO eu-smtp-delivery-143.mimecast.com) (146.101.78.143) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 11 Jan 2016 16:11:22 +0000 Received: from EUR01-HE1-obe.outbound.protection.outlook.com (mail-he1eur01lp0215.outbound.protection.outlook.com [213.199.154.215]) (Using TLS) by eu-smtp-1.mimecast.com with ESMTP id uk-mta-11-9QuGBtyIQyeN8nNggpl6zg-1; Mon, 11 Jan 2016 16:11:15 +0000 Received: from HE1PR08MB0507.eurprd08.prod.outlook.com (10.161.120.154) by HE1PR08MB0507.eurprd08.prod.outlook.com (10.161.120.154) with Microsoft SMTP Server (TLS) id 15.1.361.13; Mon, 11 Jan 2016 16:11:12 +0000 Received: from HE1PR08MB0507.eurprd08.prod.outlook.com ([10.161.120.154]) by HE1PR08MB0507.eurprd08.prod.outlook.com ([10.161.120.154]) with mapi id 15.01.0361.006; Mon, 11 Jan 2016 16:11:12 +0000 From: Bin Cheng To: "gcc-patches@gcc.gnu.org" CC: nd Subject: [PATCH PR68911]Check overflow when computing range information from loop niter bound Date: Mon, 11 Jan 2016 16:11:11 +0000 Message-ID: x-microsoft-exchange-diagnostics: 1; HE1PR08MB0507; 5:5qPhl9nfoEjQ23s+ikEwXM8NPL5xZrotJmecmm2lxIK+ueo3e2t1Ei4EV2cqfDdZocbNRO/yXkNuddLppITRyhhCJc3oTGdRzVdtRqvz7o8nTnLX9IZACraKoi1JBsUEMCNFr4Jc9NAsN1qymSpM4g==; 24:NVw72ceGKUwMSUciUq6rV7RsDTnu3oZkq7Fy7b0v5GPjpdq/whUiHj7I0R5vVypwOHyGMdrzr5nvor2+E8iwV9XyhKmUvIykjyhiBIehon4=; 20:LxPdU56DzVQa3c6a6EpQjMy2526I0dv2fEFE8bV1MmsCcnzV6D7d1FebSBYzRDdvsZXXOgRSuSg/vmkMkOffRrii77rOMvWuQnLXE/KLsTmIaV6Fl8Edm+N2C9Y6hFJ25+towVBCsb80Jz7nmM3t+/Y5C9JgWC44QSAwyAreMYI= x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:HE1PR08MB0507; x-ms-office365-filtering-correlation-id: bc67b4c1-16ec-42b7-ebbc-08d31aa1d352 nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(180628864354917); x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(102615245)(601004)(2401047)(5005006)(520078)(8121501046)(10201501046)(3002001); SRVR:HE1PR08MB0507; BCL:0; PCL:0; RULEID:; SRVR:HE1PR08MB0507; x-forefront-prvs: 0818724663 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(6009001)(189002)(164054003)(199003)(377424004)(54534003)(102836003)(122556002)(5002640100001)(229853001)(19580405001)(106116001)(92566002)(2900100001)(106356001)(33656002)(105586002)(3846002)(5008740100001)(189998001)(77096005)(2351001)(86362001)(2501003)(5003600100002)(2906002)(4326007)(10400500002)(5004730100002)(76576001)(66066001)(450100001)(586003)(40100003)(74316001)(11100500001)(1096002)(99936001)(50986999)(81156007)(97736004)(101416001)(87936001)(54356999)(110136002)(19580395003)(5001960100002)(1220700001)(6116002); DIR:OUT; SFP:1101; SCL:1; SRVR:HE1PR08MB0507; H:HE1PR08MB0507.eurprd08.prod.outlook.com; FPR:; SPF:None; PTR:InfoNoRecords; MX:1; A:1; LANG:en; spamdiagnosticoutput: 1:23 spamdiagnosticmetadata: NSPM MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-originalarrivaltime: 11 Jan 2016 16:11:11.9043 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: HE1PR08MB0507 X-MC-Unique: 9QuGBtyIQyeN8nNggpl6zg-1 X-IsSubscribed: yes Hi, A wrong code bug is reported in PR68911, which GCC generates infinite loop for below example after loop niter analysis changes. After that change, scev_probably_wraps_p identifies that e_1 in below case never overflow/wrap: : e_15 = e_1 + 1; : # e_1 = PHI if (e_1 <= 93) goto ; else goto ; The loop niter analysis gives us: Analyzing # of iterations of loop 2 exit condition [e_8, + , 1] <= 93 bounds on difference of bases: -4294967202 ... 93 result: zero if e_8 > 94 # of iterations 94 - e_8, bounded by 94 I think the analysis is good. When scev_probably_wraps_p returns false, it may imply two possible cases. CASE 1) If loop's latch gets executed, then we know the SCEV doesn't overflow/wrap during loop execution. CASE 2) If loop's latch isn't executed, i.e., the loop exits immediately at its first check on exit condition. In this case the SCEV doesn't overflow/wrap because it isn't increased at all. The real problem I think is VRP only checks scev_probably_wraps_p then assumes SCEV won't overflow/wrap after niter.bound iterations. This is not true for CASE 2). If we have a large enough starting value for e_1, for example, 0xfffffff8 in this example, e_1 is guaranteed not overflow/wrap only because the loop exits immediately, not after niter.bound interations. Here VRP assuming "e_1 + niter.bound" doesn't overflow/wrap is wrong. This patch fixes the issue by adding overflow check in range information computed for "e_1 + niter.bound". It catches overflow/wrap of the expression when loop may exit immediately. With this change, actually I think it may be possible for us to remove the call to scev_probably_wraps_p, though I didn't do that in this patch. Bootstrap and test on x86_64 and AArch64. Is it OK? Thanks, bin 2016-01-10 Bin Cheng PR tree-optimization/68911 * tree-vrp.c (adjust_range_with_scev): Check overflow in range information computed for expression "init + nit * step". gcc/testsuite/ChangeLog 2016-01-10 Bin Cheng PR tree-optimization/68911 * gcc.c-torture/execute/pr68911.c: New test. diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index acbb70b..811a7e4 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -4259,6 +4259,27 @@ adjust_range_with_scev (value_range *vr, struct loop *loop, /* Likewise if the addition did. */ if (maxvr.type == VR_RANGE) { + value_range initvr = VR_INITIALIZER; + + if (TREE_CODE (init) == SSA_NAME) + initvr = *(get_value_range (init)); + else if (is_gimple_min_invariant (init)) + set_value_range_to_value (&initvr, init, NULL); + else + return; + + /* Check if init + nit * step overflows. Though we checked + scev {init, step}_loop doesn't wrap, it is not enough + because the loop may exit immediately. Overflow could + happen in the plus expression in this case. */ + if ((dir == EV_DIR_DECREASES + && (is_negative_overflow_infinity (maxvr.min) + || compare_values (maxvr.min, initvr.min) != -1)) + || (dir == EV_DIR_GROWS + && (is_positive_overflow_infinity (maxvr.max) + || compare_values (maxvr.max, initvr.max) != 1))) + return; + tmin = maxvr.min; tmax = maxvr.max; } diff --git a/gcc/testsuite/gcc.c-torture/execute/pr68911.c b/gcc/testsuite/gcc.c-torture/execute/pr68911.c new file mode 100644 index 0000000..f245a11 --- /dev/null +++ b/gcc/testsuite/gcc.c-torture/execute/pr68911.c @@ -0,0 +1,27 @@ +extern void abort (void); + +char a; +int b, c; +short d; + +int main () +{ + unsigned e = 2; + unsigned timeout = 0; + + for (; c < 2; c++) + { + int f = ~e / 7; + if (f) + a = e = ~(b && d); + while (e < 94) + { + e++; + if (++timeout > 100) + goto die; + } + } + return 0; +die: + abort (); +}