* cfgloop.h (fix_loop_placement, can_duplicate_loop_p,

	duplicate_loop_to_header_edge, loopify, remove_path, split_loop_bb):
	Declare.
	(DLTHE_FLAG_UPDATE_FREQ): New.
	* cfgloopmanip.c (duplicate_loop, duplicate_subloops, copy_loops_to,
	loop_redirect_edge, loop_delete_branch_edge, copy_bbs, remove_bbs,
	rpe_enum_p, find_branch, alp_enum_p, add_loop, fix_loop_placements,
	fix_bb_placement, fix_bb_placements, place_new_loop,
	scale_loop_frequencies, scale_bbs_frequencies, record_exit_edges):
	New static functions.
	(fix_loop_placement, can_duplicate_loop_p,
	duplicate_loop_to_header_edge, loopify, remove_path, split_loop_bb):
	New functions.

	* cfgloop.h (loop_optimizer_init, loop_optimizer_finalize,
	unswitch_loops): Declare.
	* loop-init.c: New file.
	* loop-unswitch.c: New file.
	* Makefile.in (loop-init.o, loop-unswitch.o): New.
	* params.def (PARAM_MAX_UNSWITCH_INSNS, PARAM_MAX_UNSWITCH_LEVEL): New.
	* toplev.c (DFI_loop2): New dump.
	(flag_unswitch_loops): New.
	(lang_independent_options): Add it.
	(rest_of_compilation): Call new loop optimizer.
	(parse_options_and_default_flags): Turn flag_unswitch_loops on with -O3.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@62578 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 412 insertions, 0 deletions

diff --git a/gcc/loop-unswitch.c b/gcc/loop-unswitch.c
new file mode 100644
index 00000000000..8d6654c520e
--- /dev/null
+++ b/gcc/loop-unswitch.c
@@ -0,0 +1,412 @@
+/* Loop unswitching for GNU compiler.
+   Copyright (C) 2002 Free Software Foundation, Inc.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "rtl.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "cfgloop.h"
+#include "cfglayout.h"
+#include "params.h"
+#include "output.h"
+#include "expr.h"
+
+/* This pass moves constant conditions out of loops, duplicating the loop
+   in progres, i.e. this code:
+
+   while (loop_cond)
+     {
+       A;
+       if (cond)
+         branch1;
+       else
+	 branch2;
+       B;
+       if (cond)
+         branch3;
+       C;
+     }
+   where nothing inside the loop alters cond is transformed
+   into
+
+   if (cond)
+     {
+       while (loop_cond)
+	 {
+	   A;
+	   branch1;
+	   B;
+	   branch3;
+	   C;
+	 }
+     }
+   else
+     {
+       while (loop_cond)
+	 {
+	   A;
+	   branch2;
+	   B;
+	   C;
+	 }
+     }
+
+  Duplicating the loop might lead to code growth exponential in number of
+  branches inside loop, so we limit the number of unswitchings performed
+  in a single loop to PARAM_MAX_UNSWITCH_LEVEL.  We only perform the
+  transformation on innermost loops, as the benefit of doing it on loops
+  containing subloops would not be very large compared to complications
+  with handling this case.  */
+
+static struct loop *unswitch_loop	PARAMS ((struct loops *,
+						struct loop *, basic_block));
+static void unswitch_single_loop	PARAMS ((struct loops *, struct loop *,
+						rtx, int));
+static bool may_unswitch_on_p		PARAMS ((struct loops *, basic_block,
+						struct loop *, basic_block *));
+static rtx reversed_condition		PARAMS ((rtx));
+
+/* Main entry point.  Perform loop unswitching on all suitable LOOPS.  */
+void
+unswitch_loops (loops)
+     struct loops *loops;
+{
+  int i, num;
+  struct loop *loop;
+
+  /* Go through inner loops (only original ones).  */
+  num = loops->num;
+  
+  for (i = 1; i < num; i++)
+    {
+      /* Removed loop?  */
+      loop = loops->parray[i];
+      if (!loop)
+	continue;
+
+      if (loop->inner)
+	continue;
+
+      unswitch_single_loop (loops, loop, NULL_RTX, 0);
+#ifdef ENABLE_CHECKING
+      verify_dominators (loops->cfg.dom);
+      verify_loop_structure (loops);
+#endif
+    }
+}
+
+/* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
+   basic blocks (for what it means see comments below).  List of basic blocks
+   inside LOOP is provided in BODY to save time.  */
+static bool
+may_unswitch_on_p (loops, bb, loop, body)
+     struct loops *loops;
+     basic_block bb;
+     struct loop *loop;
+     basic_block *body;
+{
+  rtx test;
+  unsigned i;
+
+  /* BB must end in a simple conditional jump.  */
+  if (!bb->succ || !bb->succ->succ_next || bb->succ->succ_next->succ_next)
+    return false;
+  if (!any_condjump_p (bb->end))
+    return false;
+
+  /* With branches inside loop.  */
+  if (!flow_bb_inside_loop_p (loop, bb->succ->dest)
+      || !flow_bb_inside_loop_p (loop, bb->succ->succ_next->dest))
+    return false;
+
+  /* It must be executed just once each iteration (because otherwise we
+     are unable to update dominator/irreducible loop information correctly).  */
+  if (!just_once_each_iteration_p (loops, loop, bb))
+    return false;
+
+  /* Condition must be invariant.  We use just a stupid test of invariantness
+     of the condition: all used regs must not be modified inside loop body.  */
+  test = get_condition (bb->end, NULL);
+  if (!test)
+    return false;
+
+  for (i = 0; i < loop->num_nodes; i++)
+    if (modified_between_p (test, body[i]->head, NEXT_INSN (body[i]->end)))
+      return false;
+
+  return true;
+}
+
+/* Reverses CONDition; returns NULL if we cannot.  */
+static rtx
+reversed_condition (cond)
+     rtx cond;
+{
+  enum rtx_code reversed;
+  reversed = reversed_comparison_code (cond, NULL);
+  if (reversed == UNKNOWN)
+    return NULL_RTX;
+  else
+    return gen_rtx_fmt_ee (reversed,
+			   GET_MODE (cond), XEXP (cond, 0),
+			   XEXP (cond, 1));
+}
+
+/* Unswitch single LOOP.  COND_CHECKED holds list of conditions we already
+   unswitched on and are therefore known to be true in this LOOP.  NUM is
+   number of unswitchings done; do not allow it to grow too much, it is too
+   easy to create example on that the code would grow exponentially.  */
+static void
+unswitch_single_loop (loops, loop, cond_checked, num)
+     struct loops *loops;
+     struct loop *loop;
+     rtx cond_checked;
+     int num;
+{
+  basic_block *bbs, bb;
+  struct loop *nloop;
+  unsigned i;
+  int true_first;
+  rtx cond, rcond, conds, rconds, acond, split_before;
+  int always_true;
+  int always_false;
+  int repeat;
+  edge e;
+
+  /* Do not unswitch too much.  */
+  if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
+    {
+      if (rtl_dump_file)
+	fprintf (rtl_dump_file, ";; Not unswitching anymore, hit max level\n");
+      return;
+    }
+
+  /* Only unswitch innermost loops.  */
+  if (loop->inner)
+    {
+      if (rtl_dump_file)
+	fprintf (rtl_dump_file, ";; Not unswitching, not innermost loop\n");
+      return;
+    }
+  
+  /* We must be able to duplicate loop body.  */
+  if (!can_duplicate_loop_p (loop))
+    {
+      if (rtl_dump_file)
+	fprintf (rtl_dump_file, ";; Not unswitching, can't duplicate loop\n");
+      return;
+    }
+
+  /* The loop should not be too large, to limit code growth.  */
+  if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
+    {
+      if (rtl_dump_file)
+	fprintf (rtl_dump_file, ";; Not unswitching, loop too big\n");
+      return;
+    }
+  
+  /* Do not unswitch in cold areas.  */
+  if (!maybe_hot_bb_p (loop->header))
+    {
+      if (rtl_dump_file)
+	fprintf (rtl_dump_file, ";; Not unswitching, not hot area\n");
+      return;
+    }
+  
+  /* Nor if the loop usually does not roll.  */
+  if (expected_loop_iterations (loop) < 1)
+    {
+      if (rtl_dump_file)
+	fprintf (rtl_dump_file, ";; Not unswitching, loop iterations < 1\n");
+      return;
+    }
+
+  do
+    {
+      repeat = 0;
+    
+      /* Find a bb to unswitch on.  */
+      bbs = get_loop_body (loop);
+      for (i = 0; i < loop->num_nodes; i++)
+	if (may_unswitch_on_p (loops, bbs[i], loop, bbs))
+	  break;
+
+      if (i == loop->num_nodes)
+	{
+	  free (bbs);
+	  return;
+	}
+
+      if (!(cond = get_condition (bbs[i]->end, &split_before)))
+	abort ();
+      rcond = reversed_condition (cond);
+      
+      /* Check whether the result can be predicted.  */
+      always_true = 0;
+      always_false = 0;
+      for (acond = cond_checked; acond; acond = XEXP (acond, 1))
+	{
+	  if (rtx_equal_p (cond, XEXP (acond, 0)))
+	    {
+	      always_true = 1;
+	      break;
+	    }
+	  if (rtx_equal_p (rcond, XEXP (acond, 0)))
+	    {
+	      always_false = 1;
+	      break;
+	    }
+	}
+
+      if (always_true)
+	{
+	  /* Remove false path.  */
+ 	  for (e = bbs[i]->succ; !(e->flags & EDGE_FALLTHRU); e = e->succ_next);
+	  remove_path (loops, e);
+	  free (bbs);
+	  repeat = 1;
+	}
+      else if (always_false)
+	{
+	  /* Remove true path.  */
+	  for (e = bbs[i]->succ; e->flags & EDGE_FALLTHRU; e = e->succ_next);
+	  remove_path (loops, e);
+	  free (bbs);
+	  repeat = 1;
+	}
+    } while (repeat);
+ 
+  /* We found the condition we can unswitch on.  */
+  conds = alloc_EXPR_LIST (0, cond, cond_checked);
+  if (rcond)
+    rconds = alloc_EXPR_LIST (0, rcond, cond_checked);
+  else
+    rconds = cond_checked;
+
+  /* Separate condition in a single basic block.  */
+  bb = split_loop_bb (loops, bbs[i], PREV_INSN (split_before))->dest;
+  free (bbs);
+  true_first = !(bb->succ->flags & EDGE_FALLTHRU);
+  if (rtl_dump_file)
+    fprintf (rtl_dump_file, ";; Unswitching loop\n");
+
+  /* Unswitch the loop on this condition.  */
+  nloop = unswitch_loop (loops, loop, bb);
+  if (!nloop)
+  abort ();
+
+  /* Invoke itself on modified loops.  */
+  unswitch_single_loop (loops, nloop, true_first ? conds : rconds, num + 1);
+  unswitch_single_loop (loops, loop, true_first ? rconds : conds, num + 1);
+
+  free_EXPR_LIST_node (conds);
+  if (rcond)
+    free_EXPR_LIST_node (rconds);
+}
+
+/* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
+   unswitching of innermost loops.  UNSWITCH_ON must be executed in every
+   iteration, i.e. it must dominate LOOP latch, and should only contain code
+   for the condition we unswitch on.  Returns NULL if impossible, new
+   loop otherwise.  */
+static struct loop *
+unswitch_loop (loops, loop, unswitch_on)
+     struct loops *loops;
+     struct loop *loop;
+     basic_block unswitch_on;
+{
+  edge entry, e, latch_edge;
+  basic_block switch_bb, unswitch_on_alt, src;
+  struct loop *nloop;
+  sbitmap zero_bitmap;
+  int irred_flag;
+
+  /* Some sanity checking.  */
+  if (!flow_bb_inside_loop_p (loop, unswitch_on))
+    abort ();
+  if (!unswitch_on->succ || !unswitch_on->succ->succ_next ||
+      unswitch_on->succ->succ_next->succ_next)
+    abort ();
+  if (!just_once_each_iteration_p (loops, loop, unswitch_on))
+    abort ();
+  if (loop->inner)
+    abort ();
+  if (!flow_bb_inside_loop_p (loop, unswitch_on->succ->dest))
+    abort ();
+  if (!flow_bb_inside_loop_p (loop, unswitch_on->succ->succ_next->dest))
+    abort ();
+  
+  /* Will we be able to perform redirection?  */
+  if (!any_condjump_p (unswitch_on->end))
+    return NULL;
+  if (!cfg_layout_can_duplicate_bb_p (unswitch_on))
+    return NULL;
+
+  entry = loop_preheader_edge (loop);
+  
+  /* Make a copy.  */
+  src = entry->src;
+  irred_flag = src->flags & BB_IRREDUCIBLE_LOOP;
+  src->flags &= ~BB_IRREDUCIBLE_LOOP;
+  zero_bitmap = sbitmap_alloc (2);
+  sbitmap_zero (zero_bitmap);
+  if (!duplicate_loop_to_header_edge (loop, entry, loops, 1,
+	zero_bitmap, NULL, NULL, NULL, 0))
+    return NULL;
+  free (zero_bitmap);
+  src->flags |= irred_flag;
+
+  /* Record the block with condition we unswitch on.  */
+  unswitch_on_alt = RBI (unswitch_on)->copy;
+
+  /* Make a copy of the block containing the condition; we will use
+     it as switch to decide which loop we want to use.  */
+  switch_bb = cfg_layout_duplicate_bb (unswitch_on, NULL);
+  switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP;
+  switch_bb->flags |= irred_flag;
+  add_to_dominance_info (loops->cfg.dom, switch_bb);
+  RBI (unswitch_on)->copy = unswitch_on_alt;
+
+  /* Loopify from the copy of LOOP body, constructing the new loop.  */
+  for (latch_edge = RBI (loop->latch)->copy->succ;
+       latch_edge->dest != loop->header;
+       latch_edge = latch_edge->succ_next);
+  nloop = loopify (loops, latch_edge,
+		   RBI (loop->header)->copy->pred, switch_bb);
+
+  /* Remove branches that are now unreachable in new loops.  We rely on the
+     fact that cfg_layout_duplicate_bb reverses list of edges.  */
+  for (e = unswitch_on->succ->succ_next->dest->pred; e; e = e->pred_next)
+    if (e->src != unswitch_on &&
+	!dominated_by_p (loops->cfg.dom, e->src, e->dest))
+      break;
+  remove_path (loops, unswitch_on->succ);
+  remove_path (loops, unswitch_on_alt->succ);
+
+  /* One of created loops do not have to be subloop of the outer loop now,
+     so fix its placement in loop datastructure.  */
+  fix_loop_placement (loop);
+  fix_loop_placement (nloop);
+
+  return nloop;
+}