Patchwork [6/9,SMS] Support potentially infinite loop

login
register
mail settings
Submitter zhroma@ispras.ru
Date July 21, 2011, 4:30 p.m.
Message ID <1311265834-2144-7-git-send-email-zhroma@ispras.ru>
Download mbox | patch
Permalink /patch/106098/
State New
Headers show

Comments

zhroma@ispras.ru - July 21, 2011, 4:30 p.m.
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  <zhroma@ispras.ru>
	* 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(-)

Patch

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");