From patchwork Tue Jul 26 17:10:19 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bin Cheng X-Patchwork-Id: 652845 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 3rzPlS6kgfz9sdn for ; Wed, 27 Jul 2016 03:10:44 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=QR+8Otvf; 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=Kvwk9X1S7J0HYZmBi5I75MRi+xH0YQAN1ZXcI/RpSjE2qJVrNZ CXM7Z3kn5BDPiNUWTqmB3lIK8PgWKsNI7C1V1Lzd4jkxd5AsfbQ2TxAld31pHvCJ 8AXZIokjSFqc2zSA0YpnUW7irgLh87rd7tCkfaNzhlgg6ZGJ5r3cQisnc= 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=qjOKei9h1HUwB8thXTu4/ZXIrwk=; b=QR+8OtvfRnOSqEpjOOFu +3I7tzfiJbd2CRT0CgZltsOtiwWEgAvYHyYRzQQDIHMapTTcN/C1XhCFytgjRnL5 01l+LqwhCoht6Vrmxisk0rfEQBM6iJntFSQL77VFaONCQtGKgofgB1fTLbc84J0V PtAwLn7iUhi3pkbjUBvaeAY= Received: (qmail 65170 invoked by alias); 26 Jul 2016 17:10:36 -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 65156 invoked by uid 89); 26 Jul 2016 17:10:35 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.6 required=5.0 tests=AWL, BAYES_00, SPF_PASS autolearn=ham version=3.3.2 spammy=sk:number_, integer_zerop, affine_iv, !integer_zerop X-HELO: eu-smtp-delivery-143.mimecast.com Received: from eu-smtp-delivery-143.mimecast.com (HELO eu-smtp-delivery-143.mimecast.com) (207.82.80.143) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 26 Jul 2016 17:10:25 +0000 Received: from EUR02-VE1-obe.outbound.protection.outlook.com (mail-ve1eur02lp0054.outbound.protection.outlook.com [213.199.154.54]) (Using TLS) by eu-smtp-1.mimecast.com with ESMTP id uk-mta-48-6TFfne-0PkmnSnK2BsoQbQ-1; Tue, 26 Jul 2016 18:10:20 +0100 Received: from HE1PR0801MB1755.eurprd08.prod.outlook.com (10.168.150.10) by HE1PR0801MB1754.eurprd08.prod.outlook.com (10.168.150.9) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P384) id 15.1.544.10; Tue, 26 Jul 2016 17:10:19 +0000 Received: from HE1PR0801MB1755.eurprd08.prod.outlook.com ([10.168.150.10]) by HE1PR0801MB1755.eurprd08.prod.outlook.com ([10.168.150.10]) with mapi id 15.01.0544.019; Tue, 26 Jul 2016 17:10:19 +0000 From: Bin Cheng To: "gcc-patches@gcc.gnu.org" CC: nd Subject: [Patch GCC]Support constraint flags in loop structure. Date: Tue, 26 Jul 2016 17:10:19 +0000 Message-ID: x-ms-office365-filtering-correlation-id: 18d80ce8-d113-4fee-9d7e-08d3b577b8c2 x-microsoft-exchange-diagnostics: 1; HE1PR0801MB1754; 20:g9i1EZleKiEbgdrgVHVAUdqkxVdf5+6bzekqOMsAYX0daaSTk802i9Qrzc31WaG4Wgxl/DErqAt0BedZpSKFFsb6Uu8A1NlTItSYo77kWbUYrYdDVxkjUxBO8G9m4s49wzbQ6QZIJmY6GhrDDe+eutF/9M94Ewa2odlVU3FeLeY= x-microsoft-antispam: UriScan:;BCL:0;PCL:0;RULEID:;SRVR:HE1PR0801MB1754; nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(180628864354917); x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(102415321)(601004)(2401047)(5005006)(8121501046)(10201501046)(3002001)(6055026); SRVR:HE1PR0801MB1754; BCL:0; PCL:0; RULEID:; SRVR:HE1PR0801MB1754; x-forefront-prvs: 00159D1518 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(6009001)(7916002)(189002)(199003)(377424004)(97736004)(2900100001)(99936001)(77096005)(19580395003)(19580405001)(110136002)(50986999)(54356999)(5002640100001)(105586002)(87936001)(450100001)(189998001)(101416001)(66066001)(33656002)(76576001)(86362001)(122556002)(11100500001)(68736007)(9686002)(2501003)(8676002)(5003600100003)(3280700002)(81156014)(81166006)(7736002)(7696003)(229853001)(305945005)(3660700001)(7846002)(2351001)(8936002)(4326007)(2906002)(106356001)(106116001)(74316002)(10400500002)(586003)(6116002)(92566002)(102836003)(3846002); DIR:OUT; SFP:1101; SCL:1; SRVR:HE1PR0801MB1754; H:HE1PR0801MB1755.eurprd08.prod.outlook.com; FPR:; SPF:None; PTR:InfoNoRecords; MX:1; A:1; LANG:en; spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-originalarrivaltime: 26 Jul 2016 17:10:19.1716 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: HE1PR0801MB1754 X-MC-Unique: 6TFfne-0PkmnSnK2BsoQbQ-1 X-IsSubscribed: yes Hi, This patch adds support for constraint flags in loop structure. Different to existing boolean flags which are set by niter analyzer, constraint flag is mainly set by consumers and affects certain semantics of niter analyzer APIs. Currently niter APIs affected are number_of_iterations_exit* and their callers. Constraint flags are added to support handling of possible infinite loops in GCC. One typical usecase of constraint is in vectorizer, as described in patch's comment: /* ... 1) Compute niter->assumptions by calling niter analyzer API and record it as possible condition for loop versioning. 2) Clear buffered result of niter/scev analyzer. 3) Set constraint LOOP_C_FINITE assuming the loop is finite. 4) Analyze data references. Since data reference analysis depends on niter/scev analyzer, the point is that niter/scev analysis is done under circumstance of LOOP_C_FINITE constraint. 5) Version the loop with assumptions computed in step 1). 6) Vectorize the versioned loop in which assumptions is guarded to be true. 7) Update constraints in versioned loops so that niter analyzer in following passes can use it. Note consumers are usually the loop optimizers and it is consumers' responsibility to set/clear constraints correctly. Failing to do that might result in hard to track bugs in niter/scev analyzer. */ Next patch will use constraint to vectorize possible infinite loop by versioning, I would also expect possible infinite loops (loops with assumptions) can be handled by more optimizers. This patch itself doesn't change GCC behavior, bootstrap and test on x86_64. Any comments? Thanks, bin 2016-07-25 Bin Cheng * cfgloop.h (struct loop): New field constraints. (LOOP_C_INFINITE, LOOP_C_FINITE): New macros. (loop_constraint_set, loop_constraint_clr, loop_constraint_set_p): New functions. * cfgloop.c (alloc_loop): Initialize new field. * tree-ssa-loop-niter.c (number_of_iterations_exit_assumptions): Adjust niter analysis wrto loop constraints. diff --git a/gcc/cfgloop.c b/gcc/cfgloop.c index 2087b90..b5c920c 100644 --- a/gcc/cfgloop.c +++ b/gcc/cfgloop.c @@ -339,6 +339,7 @@ alloc_loop (void) loop->exits = ggc_cleared_alloc (); loop->exits->next = loop->exits->prev = loop->exits; loop->can_be_parallel = false; + loop->constraints = 0; loop->nb_iterations_upper_bound = 0; loop->nb_iterations_likely_upper_bound = 0; loop->nb_iterations_estimate = 0; diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h index dfc7525..c5936f1 100644 --- a/gcc/cfgloop.h +++ b/gcc/cfgloop.h @@ -147,6 +147,30 @@ struct GTY ((chain_next ("%h.next"))) loop { /* Auxiliary info specific to a pass. */ PTR GTY ((skip (""))) aux; + /* Different to other boolean flags which are set by niter analyzer, + constraint is set by consumers and it affects certain semantics + of niter analyzer APIs. Currently the APIs affected are functions + number_of_iterations_exit* and their callers. One typical usecase + of constraints is to vectorize possibly infinite loop: + + 1) Compute niter->assumptions by calling niter analyzer API and + record it as possible condition for loop versioning. + 2) Clear buffered result of niter/scev analyzer. + 3) Set constraint LOOP_C_FINITE assuming the loop is finite. + 4) Analyze data references. Since data reference analysis depends + on niter/scev analyzer, the point is that niter/scev analysis + is done under circumstance of LOOP_C_FINITE constraint. + 5) Version the loop with assumptions computed in step 1). + 6) Vectorize the versioned loop in which assumptions is guarded to + be true. + 7) Update constraints in versioned loops so that niter analyzer + in following passes can use it. + + Note consumers are usually the loop optimizers and it is consumers' + responsibility to set/clear constraints correctly. Failing to do + that might result in hard to track bugs in niter/scev analyzer. */ + unsigned constraints; + /* The number of times the latch of the loop is executed. This can be an INTEGER_CST, or a symbolic expression representing the number of iterations like "N - 1", or a COND_EXPR containing the runtime @@ -221,6 +245,29 @@ struct GTY ((chain_next ("%h.next"))) loop { basic_block former_header; }; +/* Set if the loop is known to be infinite. */ +#define LOOP_C_INFINITE (1 << 0) +/* Set if the loop is known to be finite without any assumptions. */ +#define LOOP_C_FINITE (1 << 1) + +static inline void +loop_constraint_set (struct loop *loop, unsigned c) +{ + loop->constraints |= c; +} + +static inline void +loop_constraint_clr (struct loop *loop, unsigned c) +{ + loop->constraints &= ~c; +} + +static inline bool +loop_constraint_set_p (struct loop *loop, unsigned c) +{ + return (loop->constraints & c) == c; +} + /* Flags for state of loop structure. */ enum { diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c index b7d7c32..b922301 100644 --- a/gcc/tree-ssa-loop-niter.c +++ b/gcc/tree-ssa-loop-niter.c @@ -2148,6 +2148,10 @@ number_of_iterations_exit_assumptions (struct loop *loop, edge exit, affine_iv iv0, iv1; bool safe; + /* Nothing to analyze if the loop is known to be infinite. */ + if (loop_constraint_set_p (loop, LOOP_C_INFINITE)) + return false; + safe = dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src); if (every_iteration && !safe) @@ -2233,6 +2237,11 @@ number_of_iterations_exit_assumptions (struct loop *loop, edge exit, niter->max = wi::to_widest (iv_niters); } + /* There is no assumptions if the loop is known to be finite. */ + if (!integer_zerop (niter->assumptions) + && loop_constraint_set_p (loop, LOOP_C_FINITE)) + niter->assumptions = boolean_true_node; + if (optimize >= 3) { niter->assumptions = simplify_using_outer_evolutions (loop,