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] Canonical iv creation


Hello,

this patch adds a new simple control variable to the loop if we detect
that the loop iterates a constant number of times.  This makes it
suitable for other optimizations (unrolling, doloop optimization).
It also directly peels completely the suitable loops, thus exposing
them to the tree level optimizations.

This fixes PR 11710 and might be relevant for PR 11706 (although
there the problem of deciding whether the inlining would actually
be profitable remains).

Zdenek

Index: ChangeLog.lno
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/ChangeLog.lno,v
retrieving revision 1.1.2.81
diff -c -3 -p -r1.1.2.81 ChangeLog.lno
*** ChangeLog.lno	11 Mar 2004 20:59:14 -0000	1.1.2.81
--- ChangeLog.lno	12 Mar 2004 01:26:48 -0000
***************
*** 1,3 ****
--- 1,35 ----
+ 2004-03-12  Zdenek Dvorak  <rakdver@atrey.karlin.mff.cuni.cz>
+ 
+ 	* tree-ssa-loop-ivcanon.o: New file.
+ 	* Makefile.in (tree-ssa-loop-ivcanon.o): Add.
+ 	* flags.h (flag_unroll_loops): Declare.
+ 	* loop-invariant.c (record_use): Fix.
+ 	* params.def (PARAM_MAX_COMPLETELY_PEELED_INSNS): Increment.
+ 	* timevar.def (TV_TREE_LOOP_IVCANON): New.
+ 	* toplev.h (flag_unroll_loops): Declaration moved to flags.h.
+ 	* tree-flow.h (enum tree_ann_type): Remove MISC_ANN.
+ 	(struct tree_ann_common_d): Add aux field.
+ 	(struct misc_ann_d): Removed.
+ 	(struct stmt_ann_d): Removed aux field.
+ 	(union tree_ann_d): Removed misc field.
+ 	(canonicalize_induction_variables): Declare.
+ 	* tree-optimize.c (init_tree_optimization_passes): Add
+ 	pass_scev_iv_canon.
+ 	* tree-pass.h (pass_scev_iv_canon): Declare.
+ 	* tree-scalar-evolution.c (scev_iv_canon, gate_scev_iv_canon,
+ 	pass_scev_iv_canon): New.
+ 	(scev_done): Run cfg cleanup.
+ 	* tree-ssa-loop-im.c (LIM_DATA, determine_invariantness_stmt,
+ 	move_computations_stmt, schedule_sm): Use aux field in common
+ 	part of annotations.
+ 	* tree-ssa-loop-manip.c (allocate_new_names, rename_op,
+ 	free_new_names): Use common aux field.
+ 	(tree_duplicate_loop_to_header_edge): Fix memory leak.
+ 	* tree-ssa.c (mark_def_sites): Fix.
+ 	* tree-vectorizer.h (set_stmt_info, vinfo_for_stmt): Use aux field in
+ 	common part of annotations.
+ 	* gcc.dg/tree-ssa/ivcanon-1.c: New test.
+ 
  2004-03-11  Zdenek Dvorak  <rakdver@atrey.karlin.mff.cuni.cz>
  
  	* Makefile.in (lambda-mat.o, lambda-trans.o, lambda-code.o): Add TM_H
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.158.2.19
diff -c -3 -p -r1.903.2.158.2.19 Makefile.in
*** Makefile.in	11 Mar 2004 20:59:13 -0000	1.903.2.158.2.19
--- Makefile.in	12 Mar 2004 01:26:48 -0000
*************** OBJS-common = \
*** 873,879 ****
   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-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	   \
--- 873,879 ----
   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	   \
*************** tree-ssa-loop-im.o : tree-ssa-loop-im.c 
*** 1618,1623 ****
--- 1618,1627 ----
     $(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
+ tree-ssa-loop-ivcanon.o : tree-ssa-loop-ivcanon.c $(TREE_FLOW_H) $(CONFIG_H) \
+    $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) cfgloop.h $(PARAMS_H) tree-inline.h \
+    output.h diagnostic.h $(TM_H) coretypes.h $(TREE_DUMP_H) flags.h \
+    tree-pass.h tree-scalar-evolution.h $(GGC_H) tree-chrec.h tree-fold-const.h
  tree-ssa-loop-ivopts.o : tree-ssa-loop-ivopts.c $(TREE_FLOW_H) $(CONFIG_H) \
     $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) cfgloop.h varray.h $(EXPR_H) \
     output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
Index: flags.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flags.h,v
retrieving revision 1.86.2.41.2.9
diff -c -3 -p -r1.86.2.41.2.9 flags.h
*** flags.h	9 Mar 2004 16:23:14 -0000	1.86.2.41.2.9
--- flags.h	12 Mar 2004 01:26:48 -0000
*************** extern int flag_prefetch_loop_arrays;
*** 291,296 ****
--- 291,299 ----
  
  extern int flag_reduce_all_givs;
  
+ /* Nonzero enables loop unrolling.  */
+ extern int flag_unroll_loops;
+ 
  /* Nonzero for -fcse-follow-jumps:
     have cse follow jumps to do a more extensive job.  */
  
Index: loop-invariant.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/loop-invariant.c,v
retrieving revision 1.1.4.3
diff -c -3 -p -r1.1.4.3 loop-invariant.c
*** loop-invariant.c	9 Mar 2004 18:21:45 -0000	1.1.4.3
--- loop-invariant.c	12 Mar 2004 01:26:48 -0000
*************** static void
*** 356,361 ****
--- 356,367 ----
  record_use (struct def *def, rtx *use, rtx insn)
  {
    struct use *u = xmalloc (sizeof (struct use));
+ 
+   if (GET_CODE (*use) == SUBREG)
+     use = &SUBREG_REG (*use);
+   if (!REG_P (*use))
+     abort ();
+ 
    u->pos = use;
    u->insn = insn;
    u->next = def->uses;
Index: params.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/params.def,v
retrieving revision 1.15.2.15.2.4
diff -c -3 -p -r1.15.2.15.2.4 params.def
*** params.def	21 Feb 2004 23:09:55 -0000	1.15.2.15.2.4
--- params.def	12 Mar 2004 01:26:48 -0000
*************** DEFPARAM(PARAM_MAX_PEEL_TIMES,
*** 183,189 ****
  DEFPARAM(PARAM_MAX_COMPLETELY_PEELED_INSNS,
  	"max-completely-peeled-insns",
  	"The maximum number of insns of a completely peeled loop",
! 	120)
  /* The maximum number of peelings of a single loop that is peeled completely.  */
  DEFPARAM(PARAM_MAX_COMPLETELY_PEEL_TIMES,
  	"max-completely-peel-times",
--- 183,189 ----
  DEFPARAM(PARAM_MAX_COMPLETELY_PEELED_INSNS,
  	"max-completely-peeled-insns",
  	"The maximum number of insns of a completely peeled loop",
! 	200)
  /* The maximum number of peelings of a single loop that is peeled completely.  */
  DEFPARAM(PARAM_MAX_COMPLETELY_PEEL_TIMES,
  	"max-completely-peel-times",
Index: timevar.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/timevar.def,v
retrieving revision 1.14.2.28.2.8
diff -c -3 -p -r1.14.2.28.2.8 timevar.def
*** timevar.def	9 Mar 2004 16:23:14 -0000	1.14.2.28.2.8
--- timevar.def	12 Mar 2004 01:26:48 -0000
*************** DEFTIMEVAR (TV_TREE_DSE		     , "tree DS
*** 87,92 ****
--- 87,93 ----
  DEFTIMEVAR (TV_TREE_LOOP	     , "tree loop optimization")
  DEFTIMEVAR (TV_TREE_LINEAR_TRANSFORM , "tree loop linear transforms")
  DEFTIMEVAR (TV_TREE_LOOP_IVOPTS	     , "tree iv optimization")
+ DEFTIMEVAR (TV_TREE_LOOP_IVCANON     , "tree canonical iv creation")
  DEFTIMEVAR (TV_TREE_VECTORIZATION    , "tree loop vectorization")
  DEFTIMEVAR (TV_TREE_CH		     , "tree copy headers")
  DEFTIMEVAR (TV_TREE_SSA_TO_NORMAL    , "tree SSA to normal")
Index: toplev.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/toplev.h,v
retrieving revision 1.87.2.12.2.3
diff -c -3 -p -r1.87.2.12.2.3 toplev.h
*** toplev.h	21 Feb 2004 23:10:01 -0000	1.87.2.12.2.3
--- toplev.h	12 Mar 2004 01:26:48 -0000
*************** extern int flag_peel_loops;
*** 117,123 ****
  extern int flag_rerun_cse_after_loop;
  extern int flag_thread_jumps;
  extern int flag_tracer;
- extern int flag_unroll_loops;
  extern int flag_unroll_all_loops;
  extern int flag_unswitch_loops;
  extern int flag_cprop_registers;
--- 117,122 ----
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.177.2.13
diff -c -3 -p -r1.1.4.177.2.13 tree-flow.h
*** tree-flow.h	9 Mar 2004 16:23:14 -0000	1.1.4.177.2.13
--- tree-flow.h	12 Mar 2004 01:26:48 -0000
*************** enum tree_ann_type
*** 46,52 ****
    TREE_ANN_COMMON,
    VAR_ANN,
    STMT_ANN,
-   MISC_ANN,
    SSA_NAME_ANN
  };
  
--- 46,51 ----
*************** struct tree_ann_common_d GTY(())
*** 54,59 ****
--- 53,61 ----
  {
    /* Annotation type.  */
    enum tree_ann_type type;
+ 
+   /* Auxiliary info specific to a pass.  */
+   PTR GTY ((skip (""))) aux;
  };
  
  /* It is advantageous to avoid things like life analysis for variables which
*************** struct dataflow_d GTY(())
*** 211,223 ****
  
  typedef struct dataflow_d *dataflow_t;
  
- struct misc_ann_d GTY(())
- {
-   struct tree_ann_common_d common;
- 
-   PTR GTY ((skip (""))) data; 
- };
- 
  struct stmt_ann_d GTY(())
  {
    struct tree_ann_common_d common;
--- 213,218 ----
*************** struct stmt_ann_d GTY(())
*** 268,276 ****
       by each pass on an as-needed basis in any order convenient for the
       pass which needs statement UIDs.  */
    unsigned int uid;
- 
-   /* Auxiliary info specific to a pass.  */
-   PTR GTY ((skip (""))) aux;
  };
  
  
--- 263,268 ----
*************** union tree_ann_d GTY((desc ("ann_type ((
*** 304,310 ****
    struct tree_ann_common_d GTY((tag ("TREE_ANN_COMMON"))) common;
    struct var_ann_d GTY((tag ("VAR_ANN"))) decl;
    struct stmt_ann_d GTY((tag ("STMT_ANN"))) stmt;
-   struct misc_ann_d GTY((tag ("MISC_ANN"))) misc;
    struct ssa_name_ann_d GTY((tag ("SSA_NAME_ANN"))) ssa_name;
  };
  
--- 296,301 ----
*************** void tree_ssa_dce_no_cfg_changes (void);
*** 607,612 ****
--- 598,604 ----
  /* In tree-ssa-loop*.c  */
  void tree_ssa_lim (struct loops *loops);
  void tree_ssa_iv_optimize (struct loops *);
+ void canonicalize_induction_variables (struct loops *loops);
  void test_unrolling_and_peeling (struct loops *loops);
  bool tree_duplicate_loop_to_header_edge (struct loop *, edge, struct loops *,
  					 unsigned int, sbitmap,
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 1.1.4.98.2.14
diff -c -3 -p -r1.1.4.98.2.14 tree-optimize.c
*** tree-optimize.c	9 Mar 2004 16:23:14 -0000	1.1.4.98.2.14
--- tree-optimize.c	12 Mar 2004 01:26:48 -0000
*************** init_tree_optimization_passes (void)
*** 325,330 ****
--- 325,331 ----
    NEXT_PASS (pass_scev_anal);
    NEXT_PASS (pass_scev_depend);
    NEXT_PASS (pass_scev_elim_checks);
+   NEXT_PASS (pass_scev_iv_canon);
    NEXT_PASS (pass_scev_linear_transform);
    NEXT_PASS (pass_ddg);
    NEXT_PASS (pass_scev_vectorize);
Index: tree-pass.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-pass.h,v
retrieving revision 1.1.4.6
diff -c -3 -p -r1.1.4.6 tree-pass.h
*** tree-pass.h	9 Mar 2004 16:23:14 -0000	1.1.4.6
--- tree-pass.h	12 Mar 2004 01:26:48 -0000
*************** extern struct tree_opt_pass pass_scev_in
*** 107,112 ****
--- 107,113 ----
  extern struct tree_opt_pass pass_scev_anal;
  extern struct tree_opt_pass pass_scev_depend;
  extern struct tree_opt_pass pass_scev_linear_transform;
+ extern struct tree_opt_pass pass_scev_iv_canon;
  extern struct tree_opt_pass pass_scev_elim_checks;
  extern struct tree_opt_pass pass_scev_vectorize;
  extern struct tree_opt_pass pass_scev_done;
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-scalar-evolution.c,v
retrieving revision 1.1.2.18
diff -c -3 -p -r1.1.2.18 tree-scalar-evolution.c
*** tree-scalar-evolution.c	9 Mar 2004 16:23:14 -0000	1.1.2.18
--- tree-scalar-evolution.c	12 Mar 2004 01:26:48 -0000
*************** scev_linear_transform (void)
*** 2776,2781 ****
--- 2776,2789 ----
    linear_transform_loops (current_loops, *scalar_evolution_info);
  }
  
+ /* Runs the canonical iv creation pass.  */
+ 
+ static void
+ scev_iv_canon (void)
+ {
+   canonicalize_induction_variables (current_loops);
+ }
+ 
  /* Runs the vectorization pass.  */
  
  static void
*************** scev_done (void)
*** 2796,2801 ****
--- 2804,2810 ----
        VARRAY_CLEAR (*scalar_evolution_info);
        VARRAY_CLEAR (*already_instantiated);
        loop_optimizer_finalize (current_loops, NULL);
+       cleanup_tree_cfg ();
        current_loops = NULL;
      }
  
*************** gate_scev_linear_transform (void)
*** 2836,2841 ****
--- 2845,2863 ----
    return current_loops && flag_tree_loop_linear != 0;
  }
  
+ static bool
+ gate_scev_iv_canon (void)
+ {
+   return (current_loops
+ 	  /* Only run this pass if
+ 	     1) We will be able to eliminate the superfluous ivs
+ 		we create.   */
+ 	  && flag_tree_loop
+ 	  /* 2) Someone at rtl level will be able to use the information
+ 		provided.  */
+ 	  && (flag_unroll_loops
+ 	      || flag_branch_on_count_reg));
+ }
  
  static bool
  gate_scev_vectorize (void)
*************** struct tree_opt_pass pass_scev_linear_tr
*** 2939,2944 ****
--- 2961,2981 ----
    TODO_dump_func                	/* todo_flags_finish */
  };
  
+ struct tree_opt_pass pass_scev_iv_canon =
+ {
+   "ivcan",				/* name */
+   gate_scev_iv_canon,			/* gate */
+   scev_iv_canon,	       		/* execute */
+   NULL,					/* sub */
+   NULL,					/* next */
+   0,					/* static_pass_number */
+   TV_TREE_LOOP_IVCANON,	  		/* tv_id */
+   PROP_cfg | PROP_ssa,			/* properties_required */
+   0,					/* properties_provided */
+   0,					/* properties_destroyed */
+   0,					/* todo_flags_start */
+   TODO_dump_func                	/* todo_flags_finish */
+ };
  
  struct tree_opt_pass pass_scev_elim_checks = 
  {
Index: tree-ssa-loop-im.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-im.c,v
retrieving revision 1.1.2.5
diff -c -3 -p -r1.1.2.5 tree-ssa-loop-im.c
*** tree-ssa-loop-im.c	27 Feb 2004 23:07:32 -0000	1.1.2.5
--- tree-ssa-loop-im.c	12 Mar 2004 01:26:48 -0000
*************** struct lim_aux_data
*** 79,85 ****
  				   well.  */
  };
  
! #define LIM_DATA(STMT) ((struct lim_aux_data *) (stmt_ann (STMT)->aux))
  
  /* Description of a use.  */
  
--- 79,85 ----
  				   well.  */
  };
  
! #define LIM_DATA(STMT) ((struct lim_aux_data *) (stmt_ann (STMT)->common.aux))
  
  /* Description of a use.  */
  
*************** determine_invariantness_stmt (struct dom
*** 432,438 ****
  	  continue;
  	}
  
!       stmt_ann (stmt)->aux = xcalloc (1, sizeof (struct lim_aux_data));
        LIM_DATA (stmt)->always_executed_in = outermost;
  
        if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
--- 432,438 ----
  	  continue;
  	}
  
!       stmt_ann (stmt)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
        LIM_DATA (stmt)->always_executed_in = outermost;
  
        if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
*************** move_computations_stmt (struct dom_walk_
*** 520,526 ****
        cost = LIM_DATA (stmt)->cost;
        level = LIM_DATA (stmt)->tgt_loop;
        free_lim_aux_data (LIM_DATA (stmt));
!       stmt_ann (stmt)->aux = NULL;
  
        if (!level)
  	{
--- 520,526 ----
        cost = LIM_DATA (stmt)->cost;
        level = LIM_DATA (stmt)->tgt_loop;
        free_lim_aux_data (LIM_DATA (stmt));
!       stmt_ann (stmt)->common.aux = NULL;
  
        if (!level)
  	{
*************** schedule_sm (struct loop *loop, edge *ex
*** 773,779 ****
    /* Emit the load & stores.  */
    load = build (MODIFY_EXPR, void_type_node, tmp_var, addr);
    modify_stmt (load);
!   stmt_ann (load)->aux = xcalloc (1, sizeof (struct lim_aux_data));
    LIM_DATA (load)->max_loop = loop;
    LIM_DATA (load)->tgt_loop = loop;
  
--- 773,779 ----
    /* Emit the load & stores.  */
    load = build (MODIFY_EXPR, void_type_node, tmp_var, addr);
    modify_stmt (load);
!   stmt_ann (load)->common.aux = xcalloc (1, sizeof (struct lim_aux_data));
    LIM_DATA (load)->max_loop = loop;
    LIM_DATA (load)->tgt_loop = loop;
  
Index: tree-ssa-loop-ivcanon.c
===================================================================
RCS file: tree-ssa-loop-ivcanon.c
diff -N tree-ssa-loop-ivcanon.c
*** /dev/null	1 Jan 1970 00:00:00 -0000
--- tree-ssa-loop-ivcanon.c	12 Mar 2004 01:26:48 -0000
***************
*** 0 ****
--- 1,402 ----
+ /* Induction variable canonicalization.
+    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.  */
+ 
+ /* This pass detects the loops that iterate a constant number of times,
+    adds a canonical induction variable (step -1, tested against 0) 
+    and replaces the exit test.  This enables the less powerful rtl
+    level analysis to use this information.
+ 
+    This might spoil the code in some cases (by increasing register pressure).
+    Note that in the case the new variable is not needed, ivopts will get rid
+    of it, so it might only be a problem when there are no other linear induction
+    variables.  In that case the created optimization possibilities are likely
+    to pay up.
+ 
+    Additionally in case we detect that it is benefitial to unroll the
+    loop completely, we do it right here to expose the optimization
+    possibilities to the following passes.  */
+ 
+ #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 "cfgloop.h"
+ #include "tree-pass.h"
+ #include "ggc.h"
+ #include "tree-fold-const.h"
+ #include "tree-chrec.h"
+ #include "tree-scalar-evolution.h"
+ #include "params.h"
+ #include "flags.h"
+ #include "tree-inline.h"
+ 
+ /* Bound on the number of iterations we try to evaluate.  */
+ 
+ #define MAX_ITERATIONS_TO_TRACK 1000
+ 
+ /* Determines a loop phi node of LOOP such that X is derived from it
+    by a chain of operations with constants.  */
+ 
+ static tree
+ chain_of_csts_start (struct loop *loop, tree x)
+ {
+   tree stmt = SSA_NAME_DEF_STMT (x);
+   basic_block bb = bb_for_stmt (stmt);
+   use_optype uses;
+ 
+   if (!bb
+       || !flow_bb_inside_loop_p (loop, bb))
+     return NULL_TREE;
+   
+   if (TREE_CODE (stmt) == PHI_NODE)
+     {
+       if (bb == loop->header)
+ 	return stmt;
+ 
+       return NULL_TREE;
+     }
+ 
+   if (TREE_CODE (stmt) != MODIFY_EXPR)
+     return NULL_TREE;
+ 
+   get_stmt_operands (stmt);
+   if (NUM_VUSES (STMT_VUSE_OPS (stmt)) > 0)
+     return NULL_TREE;
+   if (NUM_VDEFS (STMT_VDEF_OPS (stmt)) > 0)
+     return NULL_TREE;
+   if (NUM_DEFS (STMT_DEF_OPS (stmt)) > 1)
+     return NULL_TREE;
+   uses = STMT_USE_OPS (stmt);
+   if (NUM_USES (uses) != 1)
+     return NULL_TREE;
+ 
+   return chain_of_csts_start (loop, USE_OP (uses, 0));
+ }
+ 
+ /* Determines whether X is derived from a value of a phi node in LOOP
+    such that
+ 
+    * this derivation consists only from operations with constants
+    * the initial value of the phi node is constant
+    * its value in the next iteration can be derived from the current one
+      by a chain of operations with constants.  */
+ 
+ static tree
+ get_base_for (struct loop *loop, tree x)
+ {
+   tree phi, init, next;
+ 
+   if (is_gimple_min_invariant (x))
+     return x;
+ 
+   phi = chain_of_csts_start (loop, x);
+   if (!phi)
+     return NULL_TREE;
+ 
+   init = phi_element_for_edge (phi, loop_preheader_edge (loop))->def;
+   next = phi_element_for_edge (phi, loop_latch_edge (loop))->def;
+ 
+   if (!is_gimple_min_invariant (init))
+     return NULL_TREE;
+ 
+   if (chain_of_csts_start (loop, next) != phi)
+     return NULL_TREE;
+ 
+   return phi;
+ }
+ 
+ /* Evaluates value of X, provided that the value of the variable defined
+    in the loop phi node from that X is derived by operations with constants
+    is BASE.  */
+ 
+ static tree
+ get_val_for (tree x, tree base)
+ {
+   tree stmt, *op, nx, val;
+   use_optype uses;
+ 
+   if (!x)
+     return base;
+ 
+   stmt = SSA_NAME_DEF_STMT (x);
+   if (TREE_CODE (stmt) == PHI_NODE)
+     return base;
+ 
+   uses = STMT_USE_OPS (stmt);
+   op = USE_OP_PTR (uses, 0);
+ 
+   nx = *op;
+   val = get_val_for (nx, base);
+   *op = val;
+   val = fold (TREE_OPERAND (stmt, 1));
+   *op = nx;
+ 
+   return val;
+ }
+ 
+ /* Tries to count the number of iterations of LOOP by brute force.  */
+ 
+ static tree
+ loop_niter_by_eval (struct loop *loop)
+ {
+   edge exit;
+   tree cond, cnd, acnd;
+   tree op[2], val[2], next[2], aval[2], phi[2];
+   unsigned i, j;
+   enum tree_code cmp;
+ 
+   if (loop_num_exits (loop) != 1)
+     return chrec_top;
+   exit = loop_exit_edge (loop, 0);
+ 
+   cond = last_stmt (exit->src);
+   if (!cond || TREE_CODE (cond) != COND_EXPR)
+     return chrec_top;
+ 
+   cnd = COND_EXPR_COND (cond);
+   if (exit->flags & EDGE_TRUE_VALUE)
+     cnd = invert_truthvalue (cnd);
+ 
+   cmp = TREE_CODE (cnd);
+   switch (cmp)
+     {
+     case EQ_EXPR:
+     case NE_EXPR:
+     case GT_EXPR:
+     case GE_EXPR:
+     case LT_EXPR:
+     case LE_EXPR:
+       for (j = 0; j < 2; j++)
+ 	op[j] = TREE_OPERAND (cnd, j);
+       break;
+ 
+     default:
+       return chrec_top;
+     }
+ 
+   for (j = 0; j < 2; j++)
+     {
+       phi[j] = get_base_for (loop, op[j]);
+       if (!phi[j])
+ 	return chrec_top;
+     }
+ 
+   for (j = 0; j < 2; j++)
+     {
+       if (TREE_CODE (phi[j]) == PHI_NODE)
+ 	{
+ 	  val[j] = phi_element_for_edge (phi[j],
+ 					 loop_preheader_edge (loop))->def;
+ 	  next[j] = phi_element_for_edge (phi[j],
+ 					  loop_latch_edge (loop))->def;
+ 	}
+       else
+ 	{
+ 	  val[j] = phi[j];
+ 	  next[j] = NULL_TREE;
+ 	  op[j] = NULL_TREE;
+ 	}
+     }
+ 
+   for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
+     {
+       for (j = 0; j < 2; j++)
+ 	aval[j] = get_val_for (op[j], val[j]);
+ 
+       acnd = fold (build (cmp, boolean_type_node, aval[0], aval[1]));
+       if (integer_zerop (acnd))
+ 	{
+ 	  if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
+ 	    fprintf (tree_dump_file,
+ 		     "Proved that loop %d iterates %d times using brute force.\n",
+ 		     loop->num, i);
+ 	  return build_int_2 (i, 0);
+ 	}
+ 
+       for (j = 0; j < 2; j++)
+ 	val[j] = get_val_for (next[j], val[j]);
+     }
+ 
+   return chrec_top;
+ }
+ 
+ /* Adds a canonical induction variable to LOOP iterating NITER times.  */
+ 
+ static void
+ create_canonical_iv (struct loop *loop, tree niter)
+ {
+   edge exit, in;
+   tree cond, type, var;
+   block_stmt_iterator incr_at;
+   enum tree_code cmp;
+ 
+   if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
+     {
+       fprintf (tree_dump_file, "Added canonical iv to loop %d, ", loop->num);
+       print_generic_expr (tree_dump_file, niter, TDF_SLIM);
+       fprintf (tree_dump_file, " iterations.\n");
+     }
+ 
+   exit = loop_exit_edge (loop, 0);
+   cond = last_stmt (exit->src);
+   in = exit->src->succ;
+   if (in == exit)
+     in = in->succ_next;
+ 
+   type = TREE_TYPE (niter);
+   niter = fold (build (PLUS_EXPR, type,
+ 		       niter, convert (type, integer_one_node)));
+   incr_at = bsi_last (in->src);
+   create_iv (niter, convert (type, integer_minus_one_node), NULL_TREE, loop,
+ 	     &incr_at, false, NULL, &var);
+ 
+   cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
+   COND_EXPR_COND (cond) = build (cmp, boolean_type_node,
+ 				 var, convert (type, integer_zero_node));
+   modify_stmt (cond);
+ }
+ 
+ /* Computes an estimated number of insns in LOOP.  */
+ 
+ static unsigned
+ estimate_loop_size (struct loop *loop)
+ {
+   basic_block *body = get_loop_body (loop);
+   block_stmt_iterator bsi;
+   unsigned size = 0, i;
+ 
+   for (i = 0; i < loop->num_nodes; i++)
+     for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
+       size += estimate_num_insns (bsi_stmt (bsi));
+   free (body);
+ 
+   return size;
+ }
+ 
+ /* Tries to unroll LOOP completely, i.e. NITER times.  LOOPS is the
+    loop tree. */
+ 
+ static bool
+ try_unroll_loop_completely (struct loops *loops, struct loop *loop, tree niter)
+ {
+   tree max_unroll = build_int_2 (PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES),
+ 				 0);
+   unsigned n_unroll, ninsns;
+   edge exit = loop_exit_edge (loop, 0);
+   tree cond, dont_exit, do_exit;
+ 
+   if (loop->inner)
+     return false;
+ 
+   if (!integer_nonzerop (fold (build (LE_EXPR, boolean_type_node,
+ 				      niter, max_unroll))))
+     return false;
+   n_unroll = tree_low_cst (niter, 1);
+   ninsns = estimate_loop_size (loop);
+ 
+   if (n_unroll * ninsns
+       > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
+     return false;
+ 
+   if (exit->flags & EDGE_TRUE_VALUE)
+     {
+       dont_exit = boolean_false_node;
+       do_exit = boolean_true_node;
+     }
+   else
+     {
+       dont_exit = boolean_true_node;
+       do_exit = boolean_false_node;
+     }
+   cond = last_stmt (exit->src);
+     
+   if (n_unroll)
+     {
+       if (!flag_unroll_loops)
+ 	return false;
+ 
+       COND_EXPR_COND (cond) = dont_exit;
+       modify_stmt (cond);
+ 
+       if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
+ 					       loops, n_unroll, NULL,
+ 					       NULL, NULL, NULL, 0))
+ 	return false;
+     }
+   
+   COND_EXPR_COND (cond) = do_exit;
+   modify_stmt (cond);
+ 
+   if (tree_dump_file && (tree_dump_flags & TDF_DETAILS))
+     fprintf (tree_dump_file, "Unrolled loop %d completely.\n", loop->num);
+ 
+   return true;
+ }
+ 
+ /* Adds a canonical induction variable to LOOP if suitable.  LOOPS is the loops
+    tree.  */
+ 
+ static void
+ canonicalize_loop_induction_variables (struct loops *loops, struct loop *loop)
+ {
+   tree niter 
+ #if 0 /* Causes bootstrap to fail  */
+ 	  = number_of_iterations_in_loop (loop);
+ 
+   if (TREE_CODE (niter) != INTEGER_CST)
+     niter  
+ #endif
+ 	  = loop_niter_by_eval (loop);
+ 
+   if (TREE_CODE (niter) != INTEGER_CST)
+     return;
+ 
+   if (try_unroll_loop_completely (loops, loop, niter))
+     return;
+ 
+   create_canonical_iv (loop, niter);
+ }
+ 
+ /* The main entry point of the pass.  Adds canonical induction variables
+    to the suitable LOOPS.  */
+ 
+ void
+ canonicalize_induction_variables (struct loops *loops)
+ {
+   unsigned i;
+   struct loop *loop;
+ 
+   for (i = 1; i < loops->num; i++)
+     {
+       loop = loops->parray[i];
+ 
+       if (loop)
+ 	canonicalize_loop_induction_variables (loops, loop);
+     }
+ }
Index: tree-ssa-loop-manip.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-loop-manip.c,v
retrieving revision 1.1.2.3
diff -c -3 -p -r1.1.2.3 tree-ssa-loop-manip.c
*** tree-ssa-loop-manip.c	31 Jan 2004 00:47:07 -0000	1.1.2.3
--- tree-ssa-loop-manip.c	12 Mar 2004 01:26:48 -0000
*************** allocate_new_names (tree definitions, un
*** 156,175 ****
  {
    tree def;
    unsigned i;
!   struct misc_ann_d *ann;
    tree *new_names;
  
    for (; definitions; definitions = TREE_CHAIN (definitions))
      {
        def = TREE_VALUE (definitions);
!       ann = xmalloc (sizeof (struct misc_ann_d));
        new_names = xmalloc (sizeof (tree) * (ndupl + 1));
!       ann->data = new_names;
  
        for (i = 0; i <= ndupl; i++)
  	new_names[i] = make_ssa_name (SSA_NAME_VAR (def),
  				      SSA_NAME_DEF_STMT (def));
-       def->common.ann = (union tree_ann_d *) ann;
      }
  }
  
--- 156,174 ----
  {
    tree def;
    unsigned i;
!   ssa_name_ann_t ann;
    tree *new_names;
  
    for (; definitions; definitions = TREE_CHAIN (definitions))
      {
        def = TREE_VALUE (definitions);
!       ann = get_ssa_name_ann (def);
        new_names = xmalloc (sizeof (tree) * (ndupl + 1));
!       ann->common.aux = new_names;
  
        for (i = 0; i <= ndupl; i++)
  	new_names[i] = make_ssa_name (SSA_NAME_VAR (def),
  				      SSA_NAME_DEF_STMT (def));
      }
  }
  
*************** allocate_new_names (tree definitions, un
*** 180,193 ****
  static void
  rename_op (tree *op_p, bool def, tree stmt, unsigned n_copy)
  {
!   struct misc_ann_d *ann;
    tree *new_names;
  
    if (TREE_CODE (*op_p) != SSA_NAME)
      return;
  
!   ann = &(*op_p)->common.ann->misc;
!   new_names = ann ? ann->data : NULL;
  
    /* Something defined outside of the loop.  */
    if (!new_names)
--- 179,192 ----
  static void
  rename_op (tree *op_p, bool def, tree stmt, unsigned n_copy)
  {
!   ssa_name_ann_t ann;
    tree *new_names;
  
    if (TREE_CODE (*op_p) != SSA_NAME)
      return;
  
!   ann = ssa_name_ann (*op_p);
!   new_names = ann ? ann->common.aux : NULL;
  
    /* Something defined outside of the loop.  */
    if (!new_names)
*************** static void
*** 277,292 ****
  free_new_names (tree definitions, bool free_vars)
  {
    tree def;
!   struct misc_ann_d *ann;
  
    for (; definitions; definitions = TREE_CHAIN (definitions))
      {
        def = TREE_VALUE (definitions);
!       ann = &def->common.ann->misc;
  
!       free (ann->data);
!       free (ann);
!       def->common.ann = NULL;
  
        if (free_vars)
  	release_ssa_name (def);
--- 276,290 ----
  free_new_names (tree definitions, bool free_vars)
  {
    tree def;
!   ssa_name_ann_t ann;
  
    for (; definitions; definitions = TREE_CHAIN (definitions))
      {
        def = TREE_VALUE (definitions);
!       ann = ssa_name_ann (def);
  
!       free (ann->common.aux);
!       ann->common.aux = NULL;
  
        if (free_vars)
  	release_ssa_name (def);
*************** tree_duplicate_loop_to_header_edge (stru
*** 322,328 ****
    unsigned first_new_block;
    basic_block exit_block = NULL, bb;
    unsigned n_exits, i;
!   edge *exits = get_loop_exit_edges (loop, &n_exits);
    bool peeling = (e != loop_latch_edge (loop));
    edge latch, latch_copy, ae, oe;
    tree phi, arg, map, def;
--- 320,326 ----
    unsigned first_new_block;
    basic_block exit_block = NULL, bb;
    unsigned n_exits, i;
!   edge *exits;
    bool peeling = (e != loop_latch_edge (loop));
    edge latch, latch_copy, ae, oe;
    tree phi, arg, map, def;
*************** tree_duplicate_loop_to_header_edge (stru
*** 333,338 ****
--- 331,337 ----
    if (!(loops->state & LOOPS_HAVE_PREHEADERS))
      return false;
  
+   exits = get_loop_exit_edges (loop, &n_exits);
    for (i = 0; i < n_exits; i++)
      {
        /* Edges to exit can be safely ignored, since no uses may be reached
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.180.2.3
diff -c -3 -p -r1.1.4.180.2.3 tree-ssa.c
*** tree-ssa.c	21 Feb 2004 23:10:05 -0000	1.1.4.180.2.3
--- tree-ssa.c	12 Mar 2004 01:26:48 -0000
*************** mark_def_sites (struct dom_walk_data *wa
*** 622,630 ****
  	{
  	  VDEF_RESULT (vdefs, i) = VDEF_OP (vdefs, i);
  
- 	  set_def_block (VDEF_RESULT (vdefs, i), bb);
  	  if (!TEST_BIT (kills, uid))
  	    set_livein_block (VDEF_OP (vdefs, i), bb);
  	}
      }
  
--- 622,630 ----
  	{
  	  VDEF_RESULT (vdefs, i) = VDEF_OP (vdefs, i);
  
  	  if (!TEST_BIT (kills, uid))
  	    set_livein_block (VDEF_OP (vdefs, i), bb);
+ 	  set_def_block (VDEF_RESULT (vdefs, i), bb);
  	}
      }
  
Index: tree-vectorizer.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-vectorizer.h,v
retrieving revision 1.1.2.8
diff -c -3 -p -r1.1.2.8 tree-vectorizer.h
*** tree-vectorizer.h	9 Mar 2004 18:45:18 -0000	1.1.2.8
--- tree-vectorizer.h	12 Mar 2004 01:26:48 -0000
*************** static inline void
*** 88,101 ****
  set_stmt_info (stmt_ann_t ann, stmt_vec_info stmt_info)
  {
    if (ann)
!     ann->aux = (char *) stmt_info;
  }
  
  static inline stmt_vec_info
  vinfo_for_stmt (tree stmt)
  {
    stmt_ann_t ann = stmt_ann (stmt);
!   return ann ? (stmt_vec_info) ann->aux : NULL;
  }
  
  /*-----------------------------------------------------------------*/
--- 88,101 ----
  set_stmt_info (stmt_ann_t ann, stmt_vec_info stmt_info)
  {
    if (ann)
!     ann->common.aux = (char *) stmt_info;
  }
  
  static inline stmt_vec_info
  vinfo_for_stmt (tree stmt)
  {
    stmt_ann_t ann = stmt_ann (stmt);
!   return ann ? (stmt_vec_info) ann->common.aux : NULL;
  }
  
  /*-----------------------------------------------------------------*/
Index: testsuite/gcc.dg/tree-ssa/ivcanon-1.c
===================================================================
RCS file: testsuite/gcc.dg/tree-ssa/ivcanon-1.c
diff -N testsuite/gcc.dg/tree-ssa/ivcanon-1.c
*** /dev/null	1 Jan 1970 00:00:00 -0000
--- testsuite/gcc.dg/tree-ssa/ivcanon-1.c	12 Mar 2004 01:26:49 -0000
***************
*** 0 ****
--- 1,37 ----
+ /* { dg-do compile } */ 
+ /* { dg-options "-O2 -ftree-loop-optimize -fscalar-evolutions -funroll-loops -fdump-tree-optimized" } */
+ 
+ void foo(void)
+ {
+   int n = 16875;
+ 
+   while (n)
+     {
+       if (n&1)
+ 	bar (n);
+       n >>= 1;
+     }
+ }
+ 
+ static inline int power (long x, unsigned int n)
+ {
+   long y = n % 2 ? x : 1;
+ 
+   while (n >>= 1)
+     {
+       x = x * x;
+       if (n % 2)
+ 	y = y * x;
+     }
+ 
+   return y;
+ }
+ 
+ void test(long x)
+ {
+   bar (power (x, 10));
+   bar (power (x, 27));
+ }
+ 
+ /* All loops should be completely unrolled, so there should be no labels.  */
+ /* { dg-final { scan-tree-dump-times "<L" 0 "optimized"} } */


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