From patchwork Thu Jul 21 16:30:31 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Roman Zhuykov X-Patchwork-Id: 106098 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 19770B6F68 for ; Fri, 22 Jul 2011 02:31:20 +1000 (EST) Received: (qmail 12380 invoked by alias); 21 Jul 2011 16:31:17 -0000 Received: (qmail 12246 invoked by uid 22791); 21 Jul 2011 16:31:15 -0000 X-SWARE-Spam-Status: No, hits=-2.5 required=5.0 tests=AWL, BAYES_00, RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from smtp.ispras.ru (HELO smtp.ispras.ru) (83.149.198.202) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 21 Jul 2011 16:31:00 +0000 Received: from ispserv.ispras.ru (ispserv.ispras.ru [83.149.198.72]) by smtp.ispras.ru (Postfix) with ESMTP id D4A615D407D; Thu, 21 Jul 2011 20:22:39 +0400 (MSD) Received: from condor.intra.ispras.ru (winnie.ispras.ru [83.149.198.236]) by ispserv.ispras.ru (Postfix) with ESMTP id 421E83FC48; Thu, 21 Jul 2011 20:30:35 +0400 (MSD) From: zhroma@ispras.ru To: gcc-patches@gcc.gnu.org Cc: dm@ispras.ru Subject: [PATCH 6/9] [SMS] Support potentially infinite loop Date: Thu, 21 Jul 2011 20:30:31 +0400 Message-Id: <1311265834-2144-7-git-send-email-zhroma@ispras.ru> In-Reply-To: <1311265834-2144-1-git-send-email-zhroma@ispras.ru> References: <1311265834-2144-1-git-send-email-zhroma@ispras.ru> CC: Ayal Zaks 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 This patch should be applied only after previous patch. This patch allows SMS to schedule loops with non-NULL condition under which the loop is infinite. Infinite condition is an expression list and all of them should be false if we want to use niter_expr. So, if each of expressions is a simple comparison, we can check them to be false in loop versioning condition. And the optimized loop version will run only when all infinite conditions are false and number of iterations is big enough. The problem is in adding support of such a complex conditions with several conjuntions to loop_version function. To extract expression list we have to check whether we are on RTL, while these functions work both on RTL and GIMPLE. I understand that this patch is not ready for trunk "as is", but it was created to make the whole situation more clear. 2011-07-20 Roman Zhuykov * cfgloopmanip.c (loop_version): Support multiple conditions with logical conjunction on RTL level. * common.opt (fmodulo-sched-insert-infinite-checks): New flag. * modulo-sched.c (sms_schedule): Support potentially infinite loops. --- gcc/cfgloopmanip.c | 60 +++++++++++++++++++++++++++++++++++++++++++++++++-- gcc/common.opt | 4 +++ gcc/modulo-sched.c | 58 ++++++++++++++++++++++++++++++++++++++++++++------ 3 files changed, 112 insertions(+), 10 deletions(-) diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c index 1824421..d20da19 100644 --- a/gcc/cfgloopmanip.c +++ b/gcc/cfgloopmanip.c @@ -1556,9 +1556,63 @@ loop_version (struct loop *loop, Note down new head as second_head. */ second_head = entry->dest; - /* Split loop entry edge and insert new block with cond expr. */ - cond_bb = lv_adjust_loop_entry_edge (first_head, second_head, - entry, cond_expr, then_prob); + /* On rtl level support multiple conditions (with logical conjunction + between them) organized as an expr_list. */ + if (current_ir_type () != IR_GIMPLE + && GET_CODE ((rtx)cond_expr) == EXPR_LIST) + { + edge curr_edge; + basic_block bb; + int num_cond = 0; + rtx curr_cond, backward, other_cond; + + /* Reverse condition list. */ + backward = NULL_RTX; + other_cond = (rtx)cond_expr; + while (other_cond != NULL_RTX) + { + backward = gen_rtx_EXPR_LIST (VOIDmode, + XEXP (other_cond, 0), backward); + other_cond = XEXP (other_cond, 1); + num_cond++; + } + gcc_assert (num_cond > 1); + + /* Create new block to prevent many preheaders. */ + second_head = split_edge (entry); + entry = find_edge (entry->src, second_head); + + /* Starting multi split using the last condition + which is first in a reversed list. */ + cond_bb = lv_adjust_loop_entry_edge (first_head, second_head, entry, + XEXP (backward, 0), then_prob); + other_cond = XEXP (backward, 1); + bb = cond_bb; + /* Find edge entering the created bb. */ + curr_edge = find_edge (entry->src, bb); + while (other_cond != NULL_RTX) + { + curr_cond = XEXP (other_cond, 0); + other_cond = XEXP (other_cond, 1); + /* Redirect the edge to make it possible to use + lv_adjust_loop_entry_edge. */ + curr_edge = redirect_edge_and_branch (curr_edge, second_head); + gcc_assert (curr_edge && curr_edge->src == entry->src); + + /* Split using the next condition is the reversed list. + Set 100% probability in all conditions except last. */ + bb = lv_adjust_loop_entry_edge (bb, second_head, curr_edge, + curr_cond, REG_BR_PROB_BASE); + /* The next edge to process - to new condition bb. */ + curr_edge = find_edge (curr_edge->src, bb); + gcc_assert (curr_edge && curr_edge->src == entry->src); + } + } + else + /* Simply split loop entry edge and insert new block with cond expr. */ + cond_bb = lv_adjust_loop_entry_edge (first_head, second_head, + entry, cond_expr, then_prob); + if (condition_bb) *condition_bb = cond_bb; diff --git a/gcc/common.opt b/gcc/common.opt index f127936..c40725c 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -1437,6 +1437,10 @@ fmodulo-sched-allow-regmoves Common Report Var(flag_modulo_sched_allow_regmoves) Perform SMS based modulo scheduling with register moves allowed +fmodulo-sched-insert-infinite-checks +Common Report Var(flag_modulo_sched_insert_infinite_checks) +Insert expensive checks for infinite amount of loop iterations while SMS + fmove-loop-invariants Common Report Var(flag_move_loop_invariants) Init(1) Optimization Move loop invariant computations out of loops diff --git a/gcc/modulo-sched.c b/gcc/modulo-sched.c index 35d2ee4..2aeea47 100644 --- a/gcc/modulo-sched.c +++ b/gcc/modulo-sched.c @@ -1994,8 +1994,12 @@ sms_schedule (void) We want doloops to be scheduled even if analyzis shows they are nonsimple (backward compatibility). */ nonsimple_loop = !desc->simple_p; - /* We allow scheduling loop with some assumptions or infinite condition - only when unsafe_loop_optimizations flag is enabled. */ + /* Infinite number of iterations condition can be checked at runtime + to execute the right version of a loop. But this checks can + slow down the program when the loop is inside an outer one. + So, we add this checks only when an option is enabled, and allow + scheduling loop without adding checks when unsafe_loop_optimizations + flag is enabled. */ if (flag_unsafe_loop_optimizations) { desc->infinite = NULL_RTX; @@ -2003,8 +2007,20 @@ sms_schedule (void) desc->noloop_assumptions = NULL_RTX; } nonsimple_loop = nonsimple_loop || (desc->assumptions != NULL_RTX) - || (desc->noloop_assumptions != NULL_RTX) - || (desc->infinite != NULL_RTX); + || (desc->noloop_assumptions != NULL_RTX); + if (!flag_modulo_sched_insert_infinite_checks) + nonsimple_loop = nonsimple_loop || (desc->infinite != NULL_RTX); + /* Check the form of the infinite condition. */ + if (!nonsimple_loop && desc->infinite) + { + rtx r = desc->infinite; + while (r && COMPARISON_P (XEXP (r, 0))) + { + gcc_assert (GET_CODE (r) == EXPR_LIST); + r = XEXP (r, 1); + } + nonsimple_loop = (r != NULL); + } /* Only doloops can be nonsimple_loops for SMS. */ if (nonsimple_loop && !doloop_p) { @@ -2142,9 +2158,37 @@ sms_schedule (void) /* Loop versioning if the number of iterations is unknown. */ unsigned prob; rtx vers_cond; - vers_cond = gen_rtx_fmt_ee (GT, VOIDmode, nonsimple_loop ? - count_reg : desc->niter_expr, - GEN_INT (stage_count)); + + if (desc->infinite) + { + /* We have to check the number of iterations is non-infinite + before comparing it with the number of stages. So, each + condition in a desc->infinite expr list (with logical OR) + is reversed and add to a new expr list (with logical AND). */ + rtx r, temp; + vers_cond = copy_rtx (desc->infinite); + gcc_assert (desc->niter_expr); + r = vers_cond; + temp = reversed_condition (XEXP(r, 0)); + gcc_assert(temp); + XEXP (r, 0) = temp; + while (XEXP (r, 1)) + { + temp = reversed_condition (XEXP(r, 0)); + gcc_assert(temp); + XEXP (r, 0) = temp; + r = XEXP (r, 1); + } + XEXP (r, 1) = gen_rtx_EXPR_LIST (VOIDmode, + gen_rtx_fmt_ee (GT, VOIDmode, + desc->niter_expr, + GEN_INT (stage_count)), + NULL_RTX); + } + else /* Condition = (number of iters > number of stages). */ + vers_cond = gen_rtx_fmt_ee (GT, VOIDmode, nonsimple_loop ? + count_reg : desc->niter_expr, + GEN_INT (stage_count)); if (dump_file) { fprintf (dump_file, "\nLoop versioning condition:\n");