This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[lno] Unswitching on trees


Hello,

this patch adds unswitching on trees.  This should eventually replace
the rtl level unswitching (once loop versioning handles loops with
multiple exits).

Zdenek

Index: ChangeLog.lno
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.lno,v
retrieving revision 1.1.2.96
diff -c -3 -p -r1.1.2.96 ChangeLog.lno
*** ChangeLog.lno	21 Mar 2004 03:19:33 -0000	1.1.2.96
--- ChangeLog.lno	21 Mar 2004 13:30:58 -0000
***************
*** 1,3 ****
--- 1,22 ----
+ 2004-03-21  Zdenek Dvorak  <rakdver@atrey.karlin.mff.cuni.cz>
+ 
+ 	* tree-ssa-loop-unswitch.o: New file.
+ 	* Makefile.in (tree-ssa-loop-unswitch.o): Add.
+ 	(tree-ssa-loop-im.o): Add flags.h dependency.
+ 	* flags.h (flag_unswitch_loops): Declaration moved from ...
+ 	* toplev.h (flag_unswitch_loops): ... here.
+ 	* tree-flow.h (tree_ssa_loop_version): Declaration changed.
+ 	(tree_ssa_unswitch_loops, estimate_loop_size): Declare.
+ 	* tree-ssa-loop-im.c: Include flags.h.
+ 	(movement_possibility, stmt_cost, move_computations_stmt):
+ 	Handle unswitchable conditions.
+ 	* tree-ssa-loop-ivcanon.c (estimate_loop_size): Export.
+ 	* tree-ssa-loop-ivopts.c (find_interesting_uses_cond): Handle
+ 	if (0) and if (1).
+ 	* tree-ssa-loop-manip.c (tree_ssa_loop_version): Return the newly
+ 	created loop.
+ 	* tree-ssa-loop.c (tree_ssa_loop_opt): Call tree_ssa_unswitch_loops.
+ 
  2004-03-20  Zdenek Dvorak  <rakdver@atrey.karlin.mff.cuni.cz>
  
  	Merge from tree-ssa branch (lno-merge-20040321).
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.158.2.22
diff -c -3 -p -r1.903.2.158.2.22 Makefile.in
*** Makefile.in	21 Mar 2004 03:19:34 -0000	1.903.2.158.2.22
--- Makefile.in	21 Mar 2004 13:30:58 -0000
*************** OBJS-common = \
*** 876,887 ****
   tree-ssa-phiopt.o tree-ssa-forwprop.o tree-nested.o tree-ssa-dse.o	   \
   tree-ssa-dom.o domwalk.o tree-tailcall.o gimple-low.o tree-iterator.o	   \
   tree-phinodes.o tree-ssanames.o tree-sra.o tree-complex.o tree-ssa-loop.o \
   tree-vectorizer.o tree-ssa-loop-im.o tree-ssa-loop-manip.o		   \
   tree-ssa-loop-ivopts.o tree-ssa-loop-ivcanon.o tree-dg.o loop-invariant.o \
   alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o	  	   \
   cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o		   \
   cfgloopanal.o cfgloopmanip.o loop-iv.o loop-init.o loop-unswitch.o	   \
!  loop-unroll.o loop-doloop.o tree-ssa-return.o						   \
   cfgrtl.o combine.o conflict.o convert.o coverage.o cse.o cselib.o	   \
   dbxout.o debug.o df.o diagnostic.o dojump.o doloop.o dominance.o	   \
   dwarf2asm.o dwarf2out.o emit-rtl.o except.o explow.o loop-iv.o		   \
--- 876,888 ----
   tree-ssa-phiopt.o tree-ssa-forwprop.o tree-nested.o tree-ssa-dse.o	   \
   tree-ssa-dom.o domwalk.o tree-tailcall.o gimple-low.o tree-iterator.o	   \
   tree-phinodes.o tree-ssanames.o tree-sra.o tree-complex.o tree-ssa-loop.o \
+  tree-ssa-loop-unswitch.o						   \
   tree-vectorizer.o tree-ssa-loop-im.o tree-ssa-loop-manip.o		   \
   tree-ssa-loop-ivopts.o tree-ssa-loop-ivcanon.o tree-dg.o loop-invariant.o \
   alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o	  	   \
   cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o		   \
   cfgloopanal.o cfgloopmanip.o loop-iv.o loop-init.o loop-unswitch.o	   \
!  loop-unroll.o loop-doloop.o tree-ssa-return.o				   \
   cfgrtl.o combine.o conflict.o convert.o coverage.o cse.o cselib.o	   \
   dbxout.o debug.o df.o diagnostic.o dojump.o doloop.o dominance.o	   \
   dwarf2asm.o dwarf2out.o emit-rtl.o except.o explow.o loop-iv.o		   \
*************** tree-ssa-loop.o : tree-ssa-loop.c $(TREE
*** 1645,1650 ****
--- 1646,1655 ----
     output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
     tree-pass.h flags.h
  tree-ssa-loop-im.o : tree-ssa-loop-im.c $(TREE_FLOW_H) $(CONFIG_H) \
+    $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) cfgloop.h domwalk.h $(PARAMS_H)\
+    output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
+    tree-pass.h flags.h
+ tree-ssa-loop-unswitch.o : tree-ssa-loop-unswitch.c $(TREE_FLOW_H) $(CONFIG_H) \
     $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) cfgloop.h domwalk.h $(PARAMS_H)\
     output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
     tree-pass.h
Index: flags.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flags.h,v
retrieving revision 1.86.2.41.2.11
diff -c -3 -p -r1.86.2.41.2.11 flags.h
*** flags.h	21 Mar 2004 03:19:59 -0000	1.86.2.41.2.11
--- flags.h	21 Mar 2004 13:30:58 -0000
*************** extern int flag_reduce_all_givs;
*** 294,299 ****
--- 294,302 ----
  /* Nonzero enables loop unrolling.  */
  extern int flag_unroll_loops;
  
+ /* Nonzero enables loop unswitching.  */
+ extern int flag_unswitch_loops;
+ 
  /* Nonzero for -fcse-follow-jumps:
     have cse follow jumps to do a more extensive job.  */
  
Index: toplev.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.h,v
retrieving revision 1.87.2.12.2.5
diff -c -3 -p -r1.87.2.12.2.5 toplev.h
*** toplev.h	21 Mar 2004 03:20:19 -0000	1.87.2.12.2.5
--- toplev.h	21 Mar 2004 13:30:58 -0000
*************** extern int flag_rerun_cse_after_loop;
*** 121,127 ****
  extern int flag_thread_jumps;
  extern int flag_tracer;
  extern int flag_unroll_all_loops;
- extern int flag_unswitch_loops;
  extern int flag_cprop_registers;
  extern int time_report;
  extern int flag_new_regalloc;
--- 121,126 ----
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.177.2.17
diff -c -3 -p -r1.1.4.177.2.17 tree-flow.h
*** tree-flow.h	21 Mar 2004 03:20:20 -0000	1.1.4.177.2.17
--- tree-flow.h	21 Mar 2004 13:30:58 -0000
*************** bool tree_duplicate_loop_to_header_edge 
*** 606,615 ****
  void create_iv (tree, tree, tree, struct loop *, block_stmt_iterator *, bool,
  		tree *, tree *);
  void test_loop_versioning (struct loops *loops);
! bool tree_ssa_loop_version (struct loops *, struct loop *, tree);
  bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *);
  void linear_transform_loops (struct loops *, varray_type);
  void loop_commit_inserts (void);
  
  /* In tree-flow-inline.h  */
  static inline int phi_arg_from_edge (tree, edge);
--- 606,617 ----
  void create_iv (tree, tree, tree, struct loop *, block_stmt_iterator *, bool,
  		tree *, tree *);
  void test_loop_versioning (struct loops *loops);
! struct loop *tree_ssa_loop_version (struct loops *, struct loop *, tree);
  bool for_each_index (tree *, bool (*) (tree, tree *, void *), void *);
  void linear_transform_loops (struct loops *, varray_type);
  void loop_commit_inserts (void);
+ void tree_ssa_unswitch_loops (struct loops *loops);
+ unsigned estimate_loop_size (struct loop *loop);
  
  /* In tree-flow-inline.h  */
  static inline int phi_arg_from_edge (tree, edge);
Index: tree-ssa-loop-im.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-im.c,v
retrieving revision 1.1.2.9
diff -c -3 -p -r1.1.2.9 tree-ssa-loop-im.c
*** tree-ssa-loop-im.c	21 Mar 2004 03:20:22 -0000	1.1.2.9
--- tree-ssa-loop-im.c	21 Mar 2004 13:30:58 -0000
*************** Software Foundation, 59 Temple Place - S
*** 36,41 ****
--- 36,42 ----
  #include "domwalk.h"
  #include "params.h"
  #include "tree-pass.h"
+ #include "flags.h"
  
  /* A list of dependencies.  */
  
*************** movement_possibility (tree stmt)
*** 144,149 ****
--- 145,160 ----
  {
    tree lhs, rhs;
  
+   if (flag_unswitch_loops
+       && TREE_CODE (stmt) == COND_EXPR)
+     {
+       /* If we perform unswitching, force the operands of the invariant
+ 	 condition to be moved out of the loop.  */
+       get_stmt_operands (stmt);
+ 
+       return MOVE_POSSIBLE;
+     }
+ 
    if (TREE_CODE (stmt) != MODIFY_EXPR)
      return MOVE_IMPOSSIBLE;
  
*************** stmt_cost (tree stmt)
*** 245,250 ****
--- 256,265 ----
    tree lhs, rhs;
    unsigned cost = 1;
  
+   /* Always try to create possibilities for unswitching.  */
+   if (TREE_CODE (stmt) == COND_EXPR)
+     return 20;
+ 
    lhs = TREE_OPERAND (stmt, 0);
    rhs = TREE_OPERAND (stmt, 1);
  
*************** move_computations_stmt (struct dom_walk_
*** 527,532 ****
--- 542,552 ----
  	  bsi_next (&bsi);
  	  continue;
  	}
+ 
+       /* We do not really want to move conditionals out of the loop; we just
+ 	 placed it here to force its operands to be moved if neccesary.  */
+       if (TREE_CODE (stmt) == COND_EXPR)
+ 	continue;
  
        if (dump_file && (dump_flags & TDF_DETAILS))
  	{
Index: tree-ssa-loop-ivcanon.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-ivcanon.c,v
retrieving revision 1.1.2.5
diff -c -3 -p -r1.1.2.5 tree-ssa-loop-ivcanon.c
*** tree-ssa-loop-ivcanon.c	21 Mar 2004 03:20:22 -0000	1.1.2.5
--- tree-ssa-loop-ivcanon.c	21 Mar 2004 13:30:58 -0000
*************** create_canonical_iv (struct loop *loop, 
*** 319,325 ****
  
  /* Computes an estimated number of insns in LOOP.  */
  
! static unsigned
  estimate_loop_size (struct loop *loop)
  {
    basic_block *body = get_loop_body (loop);
--- 319,325 ----
  
  /* Computes an estimated number of insns in LOOP.  */
  
! unsigned
  estimate_loop_size (struct loop *loop)
  {
    basic_block *body = get_loop_body (loop);
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-ivopts.c,v
retrieving revision 1.1.2.16
diff -c -3 -p -r1.1.2.16 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c	21 Mar 2004 03:20:22 -0000	1.1.2.16
--- tree-ssa-loop-ivopts.c	21 Mar 2004 13:30:58 -0000
*************** find_interesting_uses_cond (tree stmt, t
*** 1959,1964 ****
--- 1959,1968 ----
  
    const_iv.step = NULL_TREE;
  
+   if (integer_zerop (*cond_p)
+       || integer_nonzerop (*cond_p))
+     return;
+ 
    if (TREE_CODE (*cond_p) == SSA_NAME)
      {
        op0_p = cond_p;
Index: tree-ssa-loop-manip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-manip.c,v
retrieving revision 1.1.2.5
diff -c -3 -p -r1.1.2.5 tree-ssa-loop-manip.c
*** tree-ssa-loop-manip.c	17 Mar 2004 18:39:43 -0000	1.1.2.5
--- tree-ssa-loop-manip.c	21 Mar 2004 13:30:58 -0000
*************** is the loop transformed in another way (
*** 653,698 ****
  may be a run time test for things that were not resolved by static
  analysis (overlapping ranges (anti-aliasing), alignment, etc.).  */
  
! bool
! tree_ssa_loop_version (struct loops *loops,
! 		       struct loop * loop,
! 		       tree cond_expr)
  {
    edge entry, latch_edge;
    basic_block first_head, second_head, condition_bb;
    int irred_flag;
    struct loop *nloop;
-   sbitmap zero_bitmap;
  
    /* CHECKME: Loop versioning does not handle nested loop at this point.  */
    if (loop->inner)
!     return false;
  
    /* Record entry and latch edges for the loop */
    entry = loop_preheader_edge (loop);
  
-   /* CHECKME: We split entry edge later in loop versioning. tree_split_edge() does not
-      set bb flags appropriately if entry edge is marked as EDGE_IRREDUCILE_LOOP. Skip
-      such looos for now.  */
-   if (entry->flags & EDGE_IRREDUCIBLE_LOOP)
-     return false;
- 
    /* Note down head of loop as first_head.  */
    first_head = entry->dest;
  
-   zero_bitmap = sbitmap_alloc (2);
-   sbitmap_zero (zero_bitmap);
- 
    /* Duplicate loop.  */
    irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
    entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
    if (!tree_duplicate_loop_to_header_edge (loop, entry, loops, 1,
! 					   zero_bitmap, NULL, NULL, NULL, 0))
!     return false;
! 
    entry->flags |= irred_flag;
  
- 
    /* After duplication entry edge now points to new loop head blcok.
       Note down new head as second_head.  */
    second_head = entry->dest;
--- 653,687 ----
  may be a run time test for things that were not resolved by static
  analysis (overlapping ranges (anti-aliasing), alignment, etc.).  */
  
! struct loop *
! tree_ssa_loop_version (struct loops *loops, struct loop * loop, tree cond_expr)
  {
    edge entry, latch_edge;
    basic_block first_head, second_head, condition_bb;
    int irred_flag;
    struct loop *nloop;
  
    /* CHECKME: Loop versioning does not handle nested loop at this point.  */
    if (loop->inner)
!     return NULL;
  
    /* Record entry and latch edges for the loop */
    entry = loop_preheader_edge (loop);
  
    /* Note down head of loop as first_head.  */
    first_head = entry->dest;
  
    /* Duplicate loop.  */
    irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
    entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
    if (!tree_duplicate_loop_to_header_edge (loop, entry, loops, 1,
! 					   NULL, NULL, NULL, NULL, 0))
!     {
!       entry->flags |= irred_flag;
!       return NULL;
!     }
    entry->flags |= irred_flag;
  
    /* After duplication entry edge now points to new loop head blcok.
       Note down new head as second_head.  */
    second_head = entry->dest;
*************** tree_ssa_loop_version (struct loops *loo
*** 724,732 ****
    loop_split_edge_with (loop_latch_edge (loop), NULL);
    loop_split_edge_with (loop_latch_edge (nloop), NULL);
  
!   free (zero_bitmap);
! 
!   return true;
  }
  
  
--- 713,719 ----
    loop_split_edge_with (loop_latch_edge (loop), NULL);
    loop_split_edge_with (loop_latch_edge (nloop), NULL);
  
!   return nloop;
  }
  
  
Index: tree-ssa-loop-unswitch.c
===================================================================
RCS file: tree-ssa-loop-unswitch.c
diff -N tree-ssa-loop-unswitch.c
*** /dev/null	1 Jan 1970 00:00:00 -0000
--- tree-ssa-loop-unswitch.c	21 Mar 2004 13:30:58 -0000
***************
*** 0 ****
--- 1,281 ----
+ /* Loop unswitching.
+    Copyright (C) 2004 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 "tree.h"
+ #include "rtl.h"
+ #include "tm_p.h"
+ #include "hard-reg-set.h"
+ #include "basic-block.h"
+ #include "output.h"
+ #include "diagnostic.h"
+ #include "tree-flow.h"
+ #include "tree-dump.h"
+ #include "timevar.h"
+ #include "cfgloop.h"
+ #include "domwalk.h"
+ #include "params.h"
+ #include "tree-pass.h"
+ 
+ /* This file implements the loop unswitching, i.e. transformation of loops like
+ 
+    while (A)
+      {
+        if (inv)
+          B;
+ 
+        X;
+ 
+        if (!inv)
+ 	 C;
+      }
+ 
+    where inv is the loop invariant, into
+ 
+    if (inv)
+      {
+        while (A)
+ 	 {
+            B;
+ 	   X;
+ 	 }
+      }
+    else
+      {
+        while (A)
+ 	 {
+ 	   X;
+ 	   C;
+ 	 }
+      }
+ 
+    Inv is considered invariant iff the values it compares are both invariant;
+    tree-ssa-loop-im.c ensures that all the suitable conditions are in this
+    shape.  */
+ 
+ static struct loop *tree_unswitch_loop (struct loops *, struct loop *, basic_block,
+ 				   tree);
+ static void tree_unswitch_single_loop (struct loops *, struct loop *, int);
+ static tree tree_may_unswitch_on (basic_block, struct loop *);
+ 
+ /* Main entry point.  Perform loop unswitching on all suitable LOOPS.  */
+ 
+ void
+ tree_ssa_unswitch_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;
+ 
+       tree_unswitch_single_loop (loops, loop, 0);
+ #ifdef ENABLE_CHECKING
+       verify_dominators (CDI_DOMINATORS);
+       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).  */
+ 
+ static tree
+ tree_may_unswitch_on (basic_block bb, struct loop *loop)
+ {
+   tree stmt, def, cond;
+   basic_block def_bb;
+   use_optype uses;
+   unsigned i;
+ 
+   /* BB must end in a simple conditional jump.  */
+   stmt = last_stmt (bb);
+   if (!stmt || TREE_CODE (stmt) != COND_EXPR)
+     return NULL_TREE;
+ 
+   /* Condition must be invariant.  */
+   get_stmt_operands (stmt);
+   uses = STMT_USE_OPS (stmt);
+   for (i = 0; i < NUM_USES (uses); i++)
+     {
+       def = SSA_NAME_DEF_STMT (USE_OP (uses, i));
+       def_bb = bb_for_stmt (def);
+       if (def_bb
+ 	  && flow_bb_inside_loop_p (loop, def_bb))
+ 	return NULL_TREE;
+     }
+ 
+   cond = COND_EXPR_COND (stmt);
+   /* To keep the things simple, we do not directly remove the conditions,
+      but just replace tests with 0/1.  Prevent the infinite loop where we
+      would unswitch again on such a condition.  */
+   if (integer_zerop (cond) || integer_nonzerop (cond))
+     return NULL_TREE;
+ 
+   return cond;
+ }
+ 
+ /* Simplifies COND using checks in front of the entry of the LOOP.  Just very
+    simplish (sufficient to prevent us from duplicating loop in unswitching
+    unneccesarily).  */
+ 
+ static tree
+ simplify_using_entry_checks (struct loop *loop, tree cond)
+ {
+   edge e = loop_preheader_edge (loop);
+   tree stmt;
+ 
+   while (1)
+     {
+       stmt = last_stmt (e->src);
+       if (stmt
+ 	  && TREE_CODE (stmt) == COND_EXPR
+ 	  && operand_equal_p (COND_EXPR_COND (stmt), cond, 0))
+ 	return (e->flags & EDGE_TRUE_VALUE
+ 		? boolean_true_node
+ 		: boolean_false_node);
+ 
+       if (e->src->pred->pred_next)
+ 	return cond;
+ 
+       e = e->src->pred;
+       if (e->src == ENTRY_BLOCK_PTR)
+ 	return cond;
+     }
+ }
+ 
+ /* Unswitch single LOOP.  NUM is number of unswitchings done; we do not allow
+    it to grow too much, it is too easy to create example on that the code would
+    grow exponentially.  */
+ 
+ static void
+ tree_unswitch_single_loop (struct loops *loops, struct loop *loop, int num)
+ {
+   basic_block *bbs;
+   struct loop *nloop;
+   unsigned i;
+   tree cond = NULL_TREE, stmt;
+ 
+   /* Do not unswitch too much.  */
+   if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
+     {
+       if (dump_file && (dump_flags & TDF_DETAILS))
+ 	fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
+       return;
+     }
+ 
+   /* Only unswitch innermost loops.  */
+   if (loop->inner)
+     {
+       if (dump_file && (dump_flags & TDF_DETAILS))
+ 	fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
+       return;
+     }
+ 
+   /* The loop should not be too large, to limit code growth.  */
+   if (estimate_loop_size (loop)
+       > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
+     {
+       if (dump_file && (dump_flags & TDF_DETAILS))
+ 	fprintf (dump_file, ";; Not unswitching, loop too big\n");
+       return;
+     }
+ 
+   i = 0;
+   bbs = get_loop_body (loop);
+   
+   while (1)
+     {
+       /* Find a bb to unswitch on.  */
+       for (; i < loop->num_nodes; i++)
+ 	if ((cond = tree_may_unswitch_on (bbs[i], loop)))
+ 	  break;
+ 
+       if (i == loop->num_nodes)
+ 	{
+ 	  free (bbs);
+ 	  return;
+ 	}
+ 
+       cond = simplify_using_entry_checks (loop, cond);
+       stmt = last_stmt (bbs[i]);
+       if (integer_nonzerop (cond))
+ 	{
+ 	  /* Remove false path.  */
+ 	  COND_EXPR_COND (stmt) = boolean_true_node;
+ 	}
+       else if (integer_zerop (cond))
+ 	{
+ 	  /* Remove true path.  */
+ 	  COND_EXPR_COND (stmt) = boolean_false_node;
+ 	}
+       else
+ 	break;
+ 
+       modify_stmt (stmt);
+       i++;
+     }
+ 
+   if (dump_file && (dump_flags & TDF_DETAILS))
+     fprintf (dump_file, ";; Unswitching loop\n");
+ 
+   /* Unswitch the loop on this condition.  */
+   nloop = tree_unswitch_loop (loops, loop, bbs[i], cond);
+   if (!nloop)
+     return;
+ 
+   /* Invoke itself on modified loops.  */
+   tree_unswitch_single_loop (loops, nloop, num + 1);
+   tree_unswitch_single_loop (loops, loop, num + 1);
+ }
+ 
+ /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
+    unswitching of innermost loops.  COND is the condition determining which
+    loop is entered -- the new loop is entered if COND is true.  Returns NULL
+    if impossible, new loop otherwise.  */
+ 
+ static struct loop *
+ tree_unswitch_loop (struct loops *loops, struct loop *loop,
+ 		    basic_block unswitch_on, tree cond)
+ {
+   /* 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 (loop->inner)
+     abort ();
+ 
+   return tree_ssa_loop_version (loops, loop, unshare_expr (cond));
+ }
Index: tree-ssa-loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop.c,v
retrieving revision 1.1.2.3.2.15
diff -c -3 -p -r1.1.2.3.2.15 tree-ssa-loop.c
*** tree-ssa-loop.c	21 Mar 2004 03:20:22 -0000	1.1.2.3.2.15
--- tree-ssa-loop.c	21 Mar 2004 13:30:58 -0000
*************** tree_ssa_loop_opt (void)
*** 87,92 ****
--- 87,96 ----
        /* Move the expensive loop invariants.  */
        tree_ssa_lim (loops);
  
+       /* Unswitch the loops.  */
+       if (flag_unswitch_loops)
+ 	tree_ssa_unswitch_loops (loops);
+ 
        /* Optimize the induction variables.  */
        tree_ssa_iv_optimize (loops);
  


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]