From patchwork Tue Jul 20 20:23:42 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: [5/5] Enhance region checks. Date: Tue, 20 Jul 2010 10:23:42 -0000 From: Sebastian Pop X-Patchwork-Id: 59368 Message-Id: <1279657422-17300-5-git-send-email-sebpop@gmail.com> To: gcc-patches@gcc.gnu.org Cc: gcc-graphite@googlegroups.com, Sebastian Pop 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);