From patchwork Tue Jul 20 20:23:42 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sebastian Pop X-Patchwork-Id: 59368 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 84E6B1007D1 for ; Wed, 21 Jul 2010 06:25:37 +1000 (EST) Received: (qmail 11257 invoked by alias); 20 Jul 2010 20:24:24 -0000 Received: (qmail 11045 invoked by uid 22791); 20 Jul 2010 20:24:14 -0000 X-SWARE-Spam-Status: No, hits=-1.8 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, TW_TM, T_TO_NO_BRKTS_FREEMAIL X-Spam-Check-By: sourceware.org Received: from mail-yw0-f47.google.com (HELO mail-yw0-f47.google.com) (209.85.213.47) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 20 Jul 2010 20:24:09 +0000 Received: by ywe9 with SMTP id 9so691491ywe.20 for ; Tue, 20 Jul 2010 13:24:06 -0700 (PDT) Received: by 10.150.56.8 with SMTP id e8mr888027yba.371.1279657446853; Tue, 20 Jul 2010 13:24:06 -0700 (PDT) Received: from napoca ([163.181.251.115]) by mx.google.com with ESMTPS id v6sm5318285ybm.11.2010.07.20.13.24.04 (version=TLSv1/SSLv3 cipher=RC4-MD5); Tue, 20 Jul 2010 13:24:06 -0700 (PDT) Received: by napoca (sSMTP sendmail emulation); Tue, 20 Jul 2010 15:24:03 -0500 From: Sebastian Pop To: gcc-patches@gcc.gnu.org Cc: gcc-graphite@googlegroups.com, Sebastian Pop Subject: [PATCH 5/5] Enhance region checks. Date: Tue, 20 Jul 2010 15:23:42 -0500 Message-Id: <1279657422-17300-5-git-send-email-sebpop@gmail.com> In-Reply-To: <1279657422-17300-1-git-send-email-sebpop@gmail.com> References: <1279657422-17300-1-git-send-email-sebpop@gmail.com> 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 2010-07-20 Vladimir Kargov * graphite-scop-detection.c (is_valid_stmt_p): New. (is_valid_bb_p): New. --- gcc/ChangeLog.graphite | 5 ++ gcc/graphite-scop-detection.c | 83 ++++++++++++++++++++++++++++++++++++----- 2 files changed, 78 insertions(+), 10 deletions(-) diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index 8a2eced..38708d5 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,4 +1,9 @@ 2010-07-20 Vladimir Kargov + + * graphite-scop-detection.c (is_valid_stmt_p): New. + (is_valid_bb_p): New. + +2010-07-20 Vladimir Kargov Sebastian Pop * cfgloop.c (is_loop_exit): Renamed loop_exits_to_bb_p. diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c index b53b24b..8b5759b 100644 --- a/gcc/graphite-scop-detection.c +++ b/gcc/graphite-scop-detection.c @@ -1317,20 +1317,84 @@ canonicalize_loop_closed_ssa_form (void) #endif } -/* Check if REGION is a valid SCoP. */ +/* Check if STMT in BB can be represented by the polyhedral model. + The function is currently incomplete as it requires the data + reference and SCEV representation checks added. */ + +static bool +is_valid_stmt_p (refined_region_p region ATTRIBUTE_UNUSED, + basic_block bb ATTRIBUTE_UNUSED, gimple stmt) +{ + return !gimple_has_volatile_ops (stmt) + && gimple_code (stmt) != GIMPLE_ASM + && (gimple_code (stmt) != GIMPLE_CALL + || gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)); +} + +/* Check if BB can be represented in the polyhedral model as part + of REGION. Only single-exit loops are currently supported. */ static bool -is_scop_p (refined_region_p region ATTRIBUTE_UNUSED) +is_valid_bb_p (refined_region_p region, basic_block bb) { - /* TODO: Are there any harmful bbs in the region? */ - /* TODO: Do all loops have a number of iterations that can be expressed - by an affine linear function. */ + int succ_len = VEC_length (edge, bb->succs); + gimple_stmt_iterator gsi; + + /* Perform the control flow graph validity check. */ + /* TODO: Is there only well structured control flow in the region? - * All loops have just one exit? - * All loops are detected by gcc's loop detection? - * All conditions are well nested? */ + * All loops have just one exit? + * All loops are detected by gcc's loop detection? + * All conditions are well nested? */ - return false; + /* BBs without successors or with more than 2 predecessors are currently + unsupported. */ + if (succ_len > 2 || succ_len == 0) + return false; + + /* Is BB the exiting block of a single-exit loop? */ + if (succ_len == 2) + { + struct loop *loop = bb->loop_father; + + /* Single exit loops only. */ + if (!single_exit (loop) + || !loop_exits_from_bb_p (loop, bb)) + return false; + } + + /* Are there any harmful bbs in the region? (TODO) */ + + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + if (!is_valid_stmt_p (region, bb, gsi_stmt (gsi))) + return false; + + return true; +} + + +/* Check if REGION is a valid SCoP. */ + +static bool +is_scop_p (refined_region_p region) +{ + VEC (basic_block, heap) *bblist = NULL; + int i; + basic_block bb_iter; + + get_bbs_in_region (region, &bblist); + + for (i = 0; VEC_iterate (basic_block, bblist, i, bb_iter); i++) + { + if (!is_valid_bb_p (region, bb_iter)) + return false; + + /* TODO: Do all loops have a number of iterations that can be expressed + by an affine linear function. */ + /* ??? */ + } + + return true; } /* Find in a structured way Static Control Parts (SCoP) in the current @@ -1339,7 +1403,6 @@ is_scop_p (refined_region_p region ATTRIBUTE_UNUSED) static void build_scops_new (void) { - VEC (refined_region_p, heap) *scops = VEC_alloc (refined_region_p, heap, 3); VEC (refined_region_p, heap) *check = VEC_alloc (refined_region_p, heap, 3);