[thirdparty/gcc.git] / gcc / tree-ssa-loop.c

/* Loop optimizations over tree-ssa.
   Copyright (C) 2003, 2005, 2006, 2007 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 3, 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 COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#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 "tree-pass.h"
#include "timevar.h"
#include "cfgloop.h"
#include "flags.h"
#include "tree-inline.h"
#include "tree-scalar-evolution.h"

/* Initializes the loop structures.  */

static void
tree_loop_optimizer_init (void)
{
  loop_optimizer_init (LOOPS_NORMAL
		       | LOOPS_HAVE_RECORDED_EXITS);
  rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
}

/* The loop superpass.  */

static bool
gate_tree_loop (void)
{
  return flag_tree_loop_optimize != 0;
}

struct tree_opt_pass pass_tree_loop = 
{
  "loop",				/* name */
  gate_tree_loop,			/* gate */
  NULL,					/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_TREE_LOOP,				/* tv_id */
  PROP_cfg,				/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  TODO_ggc_collect,			/* todo_flags_start */
  TODO_dump_func | TODO_verify_ssa | TODO_ggc_collect,	/* todo_flags_finish */
  0					/* letter */
};

/* Loop optimizer initialization.  */

static unsigned int
tree_ssa_loop_init (void)
{
  tree_loop_optimizer_init ();
  if (number_of_loops () <= 1)
    return 0;

  scev_initialize ();
  return 0;
}
  
struct tree_opt_pass pass_tree_loop_init = 
{
  "loopinit",				/* name */
  NULL,					/* gate */
  tree_ssa_loop_init,			/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_TREE_LOOP_INIT,			/* tv_id */
  PROP_cfg,				/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
  0					/* letter */
};

/* Loop invariant motion pass.  */

static unsigned int
tree_ssa_loop_im (void)
{
  if (number_of_loops () <= 1)
    return 0;

  tree_ssa_lim ();
  return 0;
}

static bool
gate_tree_ssa_loop_im (void)
{
  return flag_tree_loop_im != 0;
}

struct tree_opt_pass pass_lim = 
{
  "lim",				/* name */
  gate_tree_ssa_loop_im,		/* gate */
  tree_ssa_loop_im,			/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_LIM,				/* tv_id */
  PROP_cfg,				/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
  0					/* letter */
};

/* Loop unswitching pass.  */

static unsigned int
tree_ssa_loop_unswitch (void)
{
  if (number_of_loops () <= 1)
    return 0;

  return tree_ssa_unswitch_loops ();
}

static bool
gate_tree_ssa_loop_unswitch (void)
{
  return flag_unswitch_loops != 0;
}

struct tree_opt_pass pass_tree_unswitch = 
{
  "unswitch",				/* name */
  gate_tree_ssa_loop_unswitch,		/* gate */
  tree_ssa_loop_unswitch,		/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_TREE_LOOP_UNSWITCH,		/* tv_id */
  PROP_cfg,				/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  TODO_ggc_collect | TODO_dump_func
    | TODO_verify_loops,		/* todo_flags_finish */
  0					/* letter */
};

/* Predictive commoning.  */

static unsigned
run_tree_predictive_commoning (void)
{
  if (!current_loops)
    return 0;

  tree_predictive_commoning ();
  return 0;
}

static bool
gate_tree_predictive_commoning (void)
{
  return flag_predictive_commoning != 0;
}

struct tree_opt_pass pass_predcom = 
{
  "pcom",				/* name */
  gate_tree_predictive_commoning,	/* gate */
  run_tree_predictive_commoning,	/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_PREDCOM,				/* tv_id */
  PROP_cfg,				/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  TODO_dump_func | TODO_verify_loops
    | TODO_update_ssa_only_virtuals,	/* todo_flags_finish */
  0					/* letter */
};

/* Loop autovectorization.  */

static unsigned int
tree_vectorize (void)
{
  return vectorize_loops ();
}

static bool
gate_tree_vectorize (void)
{
  return flag_tree_vectorize && number_of_loops () > 1;
}

struct tree_opt_pass pass_vectorize =
{
  "vect",                               /* name */
  gate_tree_vectorize,                  /* gate */
  tree_vectorize,                       /* execute */
  NULL,                                 /* sub */
  NULL,                                 /* next */
  0,                                    /* static_pass_number */
  TV_TREE_VECTORIZATION,                /* tv_id */
  PROP_cfg | PROP_ssa,                  /* properties_required */
  0,                                    /* properties_provided */
  0,                                    /* properties_destroyed */
  TODO_verify_loops,			/* todo_flags_start */
  TODO_dump_func | TODO_update_ssa
    | TODO_ggc_collect,			/* todo_flags_finish */
  0					/* letter */
};

/* Loop nest optimizations.  */

static unsigned int
tree_linear_transform (void)
{
  if (number_of_loops () <= 1)
    return 0;

  linear_transform_loops ();
  return 0;
}

static bool
gate_tree_linear_transform (void)
{
  return flag_tree_loop_linear != 0;
}

struct tree_opt_pass pass_linear_transform =
{
  "ltrans",				/* name */
  gate_tree_linear_transform,		/* gate */
  tree_linear_transform,       		/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_TREE_LINEAR_TRANSFORM,  		/* tv_id */
  PROP_cfg | PROP_ssa,			/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  TODO_dump_func | TODO_verify_loops
    | TODO_ggc_collect,			/* todo_flags_finish */
  0				        /* letter */	
};

/* Check the correctness of the data dependence analyzers.  */

static unsigned int
check_data_deps (void)
{
  if (number_of_loops () <= 1)
    return 0;

  tree_check_data_deps ();
  return 0;
}

static bool
gate_check_data_deps (void)
{
  return flag_check_data_deps != 0;
}

struct tree_opt_pass pass_check_data_deps =
{
  "ckdd",				/* name */
  gate_check_data_deps,	        	/* gate */
  check_data_deps,       		/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_CHECK_DATA_DEPS,  	        	/* tv_id */
  PROP_cfg | PROP_ssa,			/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  TODO_dump_func,                	/* todo_flags_finish */
  0				        /* letter */	
};

/* Canonical induction variable creation pass.  */

static unsigned int
tree_ssa_loop_ivcanon (void)
{
  if (number_of_loops () <= 1)
    return 0;

  return canonicalize_induction_variables ();
}

static bool
gate_tree_ssa_loop_ivcanon (void)
{
  return flag_tree_loop_ivcanon != 0;
}

struct tree_opt_pass pass_iv_canon =
{
  "ivcanon",				/* name */
  gate_tree_ssa_loop_ivcanon,		/* gate */
  tree_ssa_loop_ivcanon,	       	/* 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_verify_loops,	/* todo_flags_finish */
  0					/* letter */
};

/* Propagation of constants using scev.  */

static bool
gate_scev_const_prop (void)
{
  return flag_tree_scev_cprop;
}

struct tree_opt_pass pass_scev_cprop =
{
  "sccp",				/* name */
  gate_scev_const_prop,			/* gate */
  scev_const_prop,	       		/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_SCEV_CONST,	  		/* tv_id */
  PROP_cfg | PROP_ssa,			/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  TODO_dump_func | TODO_cleanup_cfg
    | TODO_update_ssa_only_virtuals,
					/* todo_flags_finish */
  0					/* letter */
};

/* Remove empty loops.  */

static unsigned int
tree_ssa_empty_loop (void)
{
  if (number_of_loops () <= 1)
    return 0;

  return remove_empty_loops ();
}

struct tree_opt_pass pass_empty_loop =
{
  "empty",				/* name */
  NULL,					/* gate */
  tree_ssa_empty_loop,		       	/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_COMPLETE_UNROLL,	  		/* tv_id */
  PROP_cfg | PROP_ssa,			/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  TODO_dump_func | TODO_verify_loops 
    | TODO_ggc_collect,			/* todo_flags_finish */
  0					/* letter */
};

/* Record bounds on numbers of iterations of loops.  */

static unsigned int
tree_ssa_loop_bounds (void)
{
  if (number_of_loops () <= 1)
    return 0;

  estimate_numbers_of_iterations ();
  scev_reset ();
  return 0;
}

struct tree_opt_pass pass_record_bounds =
{
  NULL,					/* name */
  NULL,					/* gate */
  tree_ssa_loop_bounds,		       	/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_TREE_LOOP_BOUNDS,	  		/* tv_id */
  PROP_cfg | PROP_ssa,			/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  0,			              	/* todo_flags_finish */
  0					/* letter */
};

/* Complete unrolling of loops.  */

static unsigned int
tree_complete_unroll (void)
{
  if (number_of_loops () <= 1)
    return 0;

  return tree_unroll_loops_completely (flag_unroll_loops
				       || flag_peel_loops
				       || optimize >= 3);
}

static bool
gate_tree_complete_unroll (void)
{
  return true;
}

struct tree_opt_pass pass_complete_unroll =
{
  "cunroll",				/* name */
  gate_tree_complete_unroll,		/* gate */
  tree_complete_unroll,		       	/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_COMPLETE_UNROLL,	  		/* tv_id */
  PROP_cfg | PROP_ssa,			/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  TODO_dump_func | TODO_verify_loops
    | TODO_ggc_collect,			/* todo_flags_finish */
  0					/* letter */
};

/* Parallelization.  */

static bool
gate_tree_parallelize_loops (void)
{
  return flag_tree_parallelize_loops != 1;
}

static unsigned
tree_parallelize_loops (void)
{
  if (number_of_loops () <= 1)
    return 0;

  if (parallelize_loops ())
    return TODO_cleanup_cfg | TODO_rebuild_alias;
  return 0;
}

struct tree_opt_pass pass_parallelize_loops =
{
  "parloops",				/* name */
  gate_tree_parallelize_loops,		/* gate */
  tree_parallelize_loops,      		/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_TREE_PARALLELIZE_LOOPS,  		/* tv_id */
  PROP_cfg | PROP_ssa,			/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
  0				        /* letter */	
};

/* Prefetching.  */

static unsigned int
tree_ssa_loop_prefetch (void)
{
  if (number_of_loops () <= 1)
    return 0;

  return tree_ssa_prefetch_arrays ();
}

static bool
gate_tree_ssa_loop_prefetch (void)
{
  return flag_prefetch_loop_arrays != 0;
}

struct tree_opt_pass pass_loop_prefetch =
{
  "aprefetch",				/* name */
  gate_tree_ssa_loop_prefetch,		/* gate */
  tree_ssa_loop_prefetch,	       	/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_TREE_PREFETCH,	  		/* tv_id */
  PROP_cfg | PROP_ssa,			/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
  0					/* letter */
};

/* Induction variable optimizations.  */

static unsigned int
tree_ssa_loop_ivopts (void)
{
  if (number_of_loops () <= 1)
    return 0;

  tree_ssa_iv_optimize ();
  return 0;
}

static bool
gate_tree_ssa_loop_ivopts (void)
{
  return flag_ivopts != 0;
}

struct tree_opt_pass pass_iv_optimize =
{
  "ivopts",				/* name */
  gate_tree_ssa_loop_ivopts,		/* gate */
  tree_ssa_loop_ivopts,		       	/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_TREE_LOOP_IVOPTS,	  		/* tv_id */
  PROP_cfg | PROP_ssa,			/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  TODO_dump_func | TODO_verify_loops
  | TODO_update_ssa | TODO_ggc_collect,	/* todo_flags_finish */
  0					/* letter */
};

/* Loop optimizer finalization.  */

static unsigned int
tree_ssa_loop_done (void)
{
  free_numbers_of_iterations_estimates ();
  scev_finalize ();
  loop_optimizer_finalize ();
  return 0;
}
  
struct tree_opt_pass pass_tree_loop_done = 
{
  "loopdone",				/* name */
  NULL,					/* gate */
  tree_ssa_loop_done,			/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_TREE_LOOP_FINI,			/* tv_id */
  PROP_cfg,				/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  TODO_cleanup_cfg | TODO_dump_func,	/* todo_flags_finish */
  0					/* letter */
};
Commit	Line	Data
4ee9c684	1	/* Loop optimizations over tree-ssa.
355572cc	2	Copyright (C) 2003, 2005, 2006, 2007 Free Software Foundation, Inc.
4ee9c684	3
	4	This file is part of GCC.
	5
	6	GCC is free software; you can redistribute it and/or modify it
	7	under the terms of the GNU General Public License as published by the
8c4c00c1	8	Free Software Foundation; either version 3, or (at your option) any
4ee9c684	9	later version.
	10
	11	GCC is distributed in the hope that it will be useful, but WITHOUT
	12	ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	13	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	14	for more details.
	15
	16	You should have received a copy of the GNU General Public License
8c4c00c1	17	along with GCC; see the file COPYING3. If not see
8c4c00c1	18	<http://www.gnu.org/licenses/>. */
4ee9c684	19
	20	#include "config.h"
	21	#include "system.h"
	22	#include "coretypes.h"
	23	#include "tm.h"
	24	#include "tree.h"
	25	#include "rtl.h"
	26	#include "tm_p.h"
	27	#include "hard-reg-set.h"
	28	#include "basic-block.h"
	29	#include "output.h"
	30	#include "diagnostic.h"
4ee9c684	31	#include "tree-flow.h"
	32	#include "tree-dump.h"
	33	#include "tree-pass.h"
	34	#include "timevar.h"
	35	#include "cfgloop.h"
	36	#include "flags.h"
	37	#include "tree-inline.h"
c91e8223	38	#include "tree-scalar-evolution.h"
4ee9c684	39
3f5be5f4	40	/* Initializes the loop structures. */
dcb9eccb	41
88e6f696	42	static void
3f5be5f4	43	tree_loop_optimizer_init (void)
dcb9eccb	44	{
88e6f696	45	loop_optimizer_init (LOOPS_NORMAL
dce58e66	46	\| LOOPS_HAVE_RECORDED_EXITS);
095dcfa3	47	rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
dcb9eccb	48	}
	49
	50	/* The loop superpass. */
	51
	52	static bool
0526a3ff	53	gate_tree_loop (void)
dcb9eccb	54	{
	55	return flag_tree_loop_optimize != 0;
	56	}
	57
0526a3ff	58	struct tree_opt_pass pass_tree_loop =
dcb9eccb	59	{
dcb9eccb	60	"loop", /* name */
0526a3ff	61	gate_tree_loop, /* gate */
dcb9eccb	62	NULL, /* execute */
	63	NULL, /* sub */
	64	NULL, /* next */
	65	0, /* static_pass_number */
	66	TV_TREE_LOOP, /* tv_id */
	67	PROP_cfg, /* properties_required */
	68	0, /* properties_provided */
	69	0, /* properties_destroyed */
	70	TODO_ggc_collect, /* todo_flags_start */
0f9005dd	71	TODO_dump_func \| TODO_verify_ssa \| TODO_ggc_collect, /* todo_flags_finish */
0f9005dd	72	0 /* letter */
dcb9eccb	73	};
	74
	75	/* Loop optimizer initialization. */
	76
2a1990e9	77	static unsigned int
dcb9eccb	78	tree_ssa_loop_init (void)
dcb9eccb	79	{
88e6f696	80	tree_loop_optimizer_init ();
7a3bf727	81	if (number_of_loops () <= 1)
2a1990e9	82	return 0;
bb445479	83
7194de72	84	scev_initialize ();
2a1990e9	85	return 0;
dcb9eccb	86	}
dcb9eccb	87
0526a3ff	88	struct tree_opt_pass pass_tree_loop_init =
dcb9eccb	89	{
	90	"loopinit", /* name */
	91	NULL, /* gate */
	92	tree_ssa_loop_init, /* execute */
	93	NULL, /* sub */
	94	NULL, /* next */
	95	0, /* static_pass_number */
6a881b08	96	TV_TREE_LOOP_INIT, /* tv_id */
dcb9eccb	97	PROP_cfg, /* properties_required */
	98	0, /* properties_provided */
	99	0, /* properties_destroyed */
	100	0, /* todo_flags_start */
88dbf20f	101	TODO_dump_func \| TODO_verify_loops, /* todo_flags_finish */
0f9005dd	102	0 /* letter */
dcb9eccb	103	};
dcb9eccb	104
7d23383d	105	/* Loop invariant motion pass. */
7d23383d	106
2a1990e9	107	static unsigned int
7d23383d	108	tree_ssa_loop_im (void)
7d23383d	109	{
7a3bf727	110	if (number_of_loops () <= 1)
2a1990e9	111	return 0;
7d23383d	112
7194de72	113	tree_ssa_lim ();
2a1990e9	114	return 0;
7d23383d	115	}
	116
	117	static bool
	118	gate_tree_ssa_loop_im (void)
	119	{
41b5cc78	120	return flag_tree_loop_im != 0;
7d23383d	121	}
	122
	123	struct tree_opt_pass pass_lim =
	124	{
	125	"lim", /* name */
	126	gate_tree_ssa_loop_im, /* gate */
	127	tree_ssa_loop_im, /* execute */
	128	NULL, /* sub */
	129	NULL, /* next */
	130	0, /* static_pass_number */
	131	TV_LIM, /* tv_id */
	132	PROP_cfg, /* properties_required */
e12d0591	133	0, /* properties_provided */
	134	0, /* properties_destroyed */
	135	0, /* todo_flags_start */
88dbf20f	136	TODO_dump_func \| TODO_verify_loops, /* todo_flags_finish */
e12d0591	137	0 /* letter */
	138	};
	139
	140	/* Loop unswitching pass. */
	141
2a1990e9	142	static unsigned int
e12d0591	143	tree_ssa_loop_unswitch (void)
e12d0591	144	{
7a3bf727	145	if (number_of_loops () <= 1)
2a1990e9	146	return 0;
e12d0591	147
7194de72	148	return tree_ssa_unswitch_loops ();
e12d0591	149	}
	150
	151	static bool
	152	gate_tree_ssa_loop_unswitch (void)
	153	{
	154	return flag_unswitch_loops != 0;
	155	}
	156
0526a3ff	157	struct tree_opt_pass pass_tree_unswitch =
e12d0591	158	{
	159	"unswitch", /* name */
	160	gate_tree_ssa_loop_unswitch, /* gate */
	161	tree_ssa_loop_unswitch, /* execute */
	162	NULL, /* sub */
	163	NULL, /* next */
	164	0, /* static_pass_number */
	165	TV_TREE_LOOP_UNSWITCH, /* tv_id */
	166	PROP_cfg, /* properties_required */
7d23383d	167	0, /* properties_provided */
	168	0, /* properties_destroyed */
	169	0, /* todo_flags_start */
ccae4f9f	170	TODO_ggc_collect \| TODO_dump_func
ccae4f9f	171	\| TODO_verify_loops, /* todo_flags_finish */
0f9005dd	172	0 /* letter */
7d23383d	173	};
7d23383d	174
ad4a85ad	175	/* Predictive commoning. */
	176
	177	static unsigned
	178	run_tree_predictive_commoning (void)
	179	{
	180	if (!current_loops)
	181	return 0;
	182
	183	tree_predictive_commoning ();
	184	return 0;
	185	}
	186
	187	static bool
	188	gate_tree_predictive_commoning (void)
	189	{
	190	return flag_predictive_commoning != 0;
	191	}
	192
	193	struct tree_opt_pass pass_predcom =
	194	{
	195	"pcom", /* name */
	196	gate_tree_predictive_commoning, /* gate */
	197	run_tree_predictive_commoning, /* execute */
	198	NULL, /* sub */
	199	NULL, /* next */
	200	0, /* static_pass_number */
	201	TV_PREDCOM, /* tv_id */
	202	PROP_cfg, /* properties_required */
	203	0, /* properties_provided */
	204	0, /* properties_destroyed */
	205	0, /* todo_flags_start */
	206	TODO_dump_func \| TODO_verify_loops
	207	\| TODO_update_ssa_only_virtuals, /* todo_flags_finish */
	208	0 /* letter */
	209	};
	210
c91e8223	211	/* Loop autovectorization. */
c91e8223	212
2a1990e9	213	static unsigned int
c91e8223	214	tree_vectorize (void)
c91e8223	215	{
7194de72	216	return vectorize_loops ();
c91e8223	217	}
	218
	219	static bool
	220	gate_tree_vectorize (void)
	221	{
7a3bf727	222	return flag_tree_vectorize && number_of_loops () > 1;
c91e8223	223	}
	224
	225	struct tree_opt_pass pass_vectorize =
	226	{
	227	"vect", /* name */
	228	gate_tree_vectorize, /* gate */
	229	tree_vectorize, /* execute */
	230	NULL, /* sub */
	231	NULL, /* next */
	232	0, /* static_pass_number */
	233	TV_TREE_VECTORIZATION, /* tv_id */
	234	PROP_cfg \| PROP_ssa, /* properties_required */
	235	0, /* properties_provided */
	236	0, /* properties_destroyed */
1b1e5627	237	TODO_verify_loops, /* todo_flags_start */
ccae4f9f	238	TODO_dump_func \| TODO_update_ssa
ccae4f9f	239	\| TODO_ggc_collect, /* todo_flags_finish */
0f9005dd	240	0 /* letter */
c91e8223	241	};
c91e8223	242
60cfcb79	243	/* Loop nest optimizations. */
60cfcb79	244
2a1990e9	245	static unsigned int
60cfcb79	246	tree_linear_transform (void)
60cfcb79	247	{
7a3bf727	248	if (number_of_loops () <= 1)
2a1990e9	249	return 0;
60cfcb79	250
7194de72	251	linear_transform_loops ();
2a1990e9	252	return 0;
60cfcb79	253	}
	254
	255	static bool
	256	gate_tree_linear_transform (void)
	257	{
	258	return flag_tree_loop_linear != 0;
	259	}
	260
	261	struct tree_opt_pass pass_linear_transform =
	262	{
	263	"ltrans", /* name */
	264	gate_tree_linear_transform, /* gate */
	265	tree_linear_transform, /* execute */
	266	NULL, /* sub */
	267	NULL, /* next */
	268	0, /* static_pass_number */
	269	TV_TREE_LINEAR_TRANSFORM, /* tv_id */
	270	PROP_cfg \| PROP_ssa, /* properties_required */
	271	0, /* properties_provided */
	272	0, /* properties_destroyed */
	273	0, /* todo_flags_start */
ccae4f9f	274	TODO_dump_func \| TODO_verify_loops
ccae4f9f	275	\| TODO_ggc_collect, /* todo_flags_finish */
60cfcb79	276	0 /* letter */
	277	};
	278
355572cc	279	/* Check the correctness of the data dependence analyzers. */
	280
	281	static unsigned int
	282	check_data_deps (void)
	283	{
7a3bf727	284	if (number_of_loops () <= 1)
355572cc	285	return 0;
	286
	287	tree_check_data_deps ();
	288	return 0;
	289	}
	290
	291	static bool
	292	gate_check_data_deps (void)
	293	{
	294	return flag_check_data_deps != 0;
	295	}
	296
	297	struct tree_opt_pass pass_check_data_deps =
	298	{
	299	"ckdd", /* name */
	300	gate_check_data_deps, /* gate */
	301	check_data_deps, /* execute */
	302	NULL, /* sub */
	303	NULL, /* next */
	304	0, /* static_pass_number */
	305	TV_CHECK_DATA_DEPS, /* tv_id */
	306	PROP_cfg \| PROP_ssa, /* properties_required */
	307	0, /* properties_provided */
	308	0, /* properties_destroyed */
	309	0, /* todo_flags_start */
	310	TODO_dump_func, /* todo_flags_finish */
	311	0 /* letter */
	312	};
	313
bb445479	314	/* Canonical induction variable creation pass. */
bb445479	315
2a1990e9	316	static unsigned int
bb445479	317	tree_ssa_loop_ivcanon (void)
bb445479	318	{
7a3bf727	319	if (number_of_loops () <= 1)
2a1990e9	320	return 0;
bb445479	321
7194de72	322	return canonicalize_induction_variables ();
bb445479	323	}
	324
	325	static bool
	326	gate_tree_ssa_loop_ivcanon (void)
	327	{
41b5cc78	328	return flag_tree_loop_ivcanon != 0;
bb445479	329	}
	330
	331	struct tree_opt_pass pass_iv_canon =
	332	{
	333	"ivcanon", /* name */
	334	gate_tree_ssa_loop_ivcanon, /* gate */
	335	tree_ssa_loop_ivcanon, /* execute */
	336	NULL, /* sub */
	337	NULL, /* next */
	338	0, /* static_pass_number */
	339	TV_TREE_LOOP_IVCANON, /* tv_id */
	340	PROP_cfg \| PROP_ssa, /* properties_required */
	341	0, /* properties_provided */
	342	0, /* properties_destroyed */
	343	0, /* todo_flags_start */
88dbf20f	344	TODO_dump_func \| TODO_verify_loops, /* todo_flags_finish */
10fec820	345	0 /* letter */
	346	};
	347
	348	/* Propagation of constants using scev. */
	349
	350	static bool
	351	gate_scev_const_prop (void)
	352	{
2a6e95ba	353	return flag_tree_scev_cprop;
10fec820	354	}
	355
	356	struct tree_opt_pass pass_scev_cprop =
	357	{
	358	"sccp", /* name */
	359	gate_scev_const_prop, /* gate */
	360	scev_const_prop, /* execute */
	361	NULL, /* sub */
	362	NULL, /* next */
	363	0, /* static_pass_number */
	364	TV_SCEV_CONST, /* tv_id */
	365	PROP_cfg \| PROP_ssa, /* properties_required */
	366	0, /* properties_provided */
	367	0, /* properties_destroyed */
	368	0, /* todo_flags_start */
bc1002e9	369	TODO_dump_func \| TODO_cleanup_cfg
bc1002e9	370	\| TODO_update_ssa_only_virtuals,
bd017bec	371	/* todo_flags_finish */
8feba661	372	0 /* letter */
	373	};
	374
	375	/* Remove empty loops. */
	376
2a1990e9	377	static unsigned int
8feba661	378	tree_ssa_empty_loop (void)
8feba661	379	{
7a3bf727	380	if (number_of_loops () <= 1)
2a1990e9	381	return 0;
8feba661	382
7194de72	383	return remove_empty_loops ();
8feba661	384	}
	385
	386	struct tree_opt_pass pass_empty_loop =
	387	{
	388	"empty", /* name */
	389	NULL, /* gate */
	390	tree_ssa_empty_loop, /* execute */
	391	NULL, /* sub */
	392	NULL, /* next */
	393	0, /* static_pass_number */
	394	TV_COMPLETE_UNROLL, /* tv_id */
	395	PROP_cfg \| PROP_ssa, /* properties_required */
	396	0, /* properties_provided */
	397	0, /* properties_destroyed */
	398	0, /* todo_flags_start */
ccae4f9f	399	TODO_dump_func \| TODO_verify_loops
ccae4f9f	400	\| TODO_ggc_collect, /* todo_flags_finish */
0f9005dd	401	0 /* letter */
bb445479	402	};
bb445479	403
41fc6ce4	404	/* Record bounds on numbers of iterations of loops. */
41fc6ce4	405
2a1990e9	406	static unsigned int
41fc6ce4	407	tree_ssa_loop_bounds (void)
41fc6ce4	408	{
7a3bf727	409	if (number_of_loops () <= 1)
2a1990e9	410	return 0;
41fc6ce4	411
7194de72	412	estimate_numbers_of_iterations ();
41fc6ce4	413	scev_reset ();
2a1990e9	414	return 0;
41fc6ce4	415	}
	416
	417	struct tree_opt_pass pass_record_bounds =
	418	{
b800e533	419	NULL, /* name */
41fc6ce4	420	NULL, /* gate */
	421	tree_ssa_loop_bounds, /* execute */
	422	NULL, /* sub */
	423	NULL, /* next */
	424	0, /* static_pass_number */
0332ea54	425	TV_TREE_LOOP_BOUNDS, /* tv_id */
41fc6ce4	426	PROP_cfg \| PROP_ssa, /* properties_required */
	427	0, /* properties_provided */
	428	0, /* properties_destroyed */
	429	0, /* todo_flags_start */
	430	0, /* todo_flags_finish */
	431	0 /* letter */
	432	};
	433
bb445479	434	/* Complete unrolling of loops. */
bb445479	435
2a1990e9	436	static unsigned int
bb445479	437	tree_complete_unroll (void)
bb445479	438	{
7a3bf727	439	if (number_of_loops () <= 1)
2a1990e9	440	return 0;
bb445479	441
7194de72	442	return tree_unroll_loops_completely (flag_unroll_loops
	443	\|\| flag_peel_loops
	444	\|\| optimize >= 3);
bb445479	445	}
	446
	447	static bool
	448	gate_tree_complete_unroll (void)
	449	{
604f7b8a	450	return true;
bb445479	451	}
	452
	453	struct tree_opt_pass pass_complete_unroll =
	454	{
	455	"cunroll", /* name */
	456	gate_tree_complete_unroll, /* gate */
	457	tree_complete_unroll, /* execute */
	458	NULL, /* sub */
	459	NULL, /* next */
	460	0, /* static_pass_number */
	461	TV_COMPLETE_UNROLL, /* tv_id */
	462	PROP_cfg \| PROP_ssa, /* properties_required */
dec41e98	463	0, /* properties_provided */
	464	0, /* properties_destroyed */
	465	0, /* todo_flags_start */
ccae4f9f	466	TODO_dump_func \| TODO_verify_loops
ccae4f9f	467	\| TODO_ggc_collect, /* todo_flags_finish */
0f9005dd	468	0 /* letter */
dec41e98	469	};
dec41e98	470
28c92cbb	471	/* Parallelization. */
	472
	473	static bool
	474	gate_tree_parallelize_loops (void)
	475	{
	476	return flag_tree_parallelize_loops != 1;
	477	}
	478
	479	static unsigned
	480	tree_parallelize_loops (void)
	481	{
	482	if (number_of_loops () <= 1)
	483	return 0;
	484
	485	if (parallelize_loops ())
	486	return TODO_cleanup_cfg \| TODO_rebuild_alias;
	487	return 0;
	488	}
	489
	490	struct tree_opt_pass pass_parallelize_loops =
	491	{
	492	"parloops", /* name */
	493	gate_tree_parallelize_loops, /* gate */
	494	tree_parallelize_loops, /* execute */
	495	NULL, /* sub */
	496	NULL, /* next */
	497	0, /* static_pass_number */
	498	TV_TREE_PARALLELIZE_LOOPS, /* tv_id */
	499	PROP_cfg \| PROP_ssa, /* properties_required */
	500	0, /* properties_provided */
	501	0, /* properties_destroyed */
	502	0, /* todo_flags_start */
	503	TODO_dump_func \| TODO_verify_loops, /* todo_flags_finish */
	504	0 /* letter */
	505	};
	506
b30560de	507	/* Prefetching. */
b30560de	508
2a1990e9	509	static unsigned int
b30560de	510	tree_ssa_loop_prefetch (void)
b30560de	511	{
7a3bf727	512	if (number_of_loops () <= 1)
2a1990e9	513	return 0;
b30560de	514
7194de72	515	return tree_ssa_prefetch_arrays ();
b30560de	516	}
	517
	518	static bool
	519	gate_tree_ssa_loop_prefetch (void)
	520	{
4f87b914	521	return flag_prefetch_loop_arrays != 0;
b30560de	522	}
	523
	524	struct tree_opt_pass pass_loop_prefetch =
	525	{
1da72d7c	526	"aprefetch", /* name */
b30560de	527	gate_tree_ssa_loop_prefetch, /* gate */
	528	tree_ssa_loop_prefetch, /* execute */
	529	NULL, /* sub */
	530	NULL, /* next */
	531	0, /* static_pass_number */
	532	TV_TREE_PREFETCH, /* tv_id */
	533	PROP_cfg \| PROP_ssa, /* properties_required */
	534	0, /* properties_provided */
	535	0, /* properties_destroyed */
	536	0, /* todo_flags_start */
	537	TODO_dump_func \| TODO_verify_loops, /* todo_flags_finish */
	538	0 /* letter */
	539	};
	540
dec41e98	541	/* Induction variable optimizations. */
dec41e98	542
2a1990e9	543	static unsigned int
dec41e98	544	tree_ssa_loop_ivopts (void)
dec41e98	545	{
7a3bf727	546	if (number_of_loops () <= 1)
2a1990e9	547	return 0;
dec41e98	548
7194de72	549	tree_ssa_iv_optimize ();
2a1990e9	550	return 0;
dec41e98	551	}
	552
	553	static bool
	554	gate_tree_ssa_loop_ivopts (void)
	555	{
	556	return flag_ivopts != 0;
	557	}
	558
	559	struct tree_opt_pass pass_iv_optimize =
	560	{
	561	"ivopts", /* name */
	562	gate_tree_ssa_loop_ivopts, /* gate */
	563	tree_ssa_loop_ivopts, /* execute */
	564	NULL, /* sub */
	565	NULL, /* next */
	566	0, /* static_pass_number */
	567	TV_TREE_LOOP_IVOPTS, /* tv_id */
	568	PROP_cfg \| PROP_ssa, /* properties_required */
bb445479	569	0, /* properties_provided */
	570	0, /* properties_destroyed */
	571	0, /* todo_flags_start */
ccae4f9f	572	TODO_dump_func \| TODO_verify_loops
ccae4f9f	573	\| TODO_update_ssa \| TODO_ggc_collect, /* todo_flags_finish */
0f9005dd	574	0 /* letter */
bb445479	575	};
bb445479	576
dcb9eccb	577	/* Loop optimizer finalization. */
dcb9eccb	578
2a1990e9	579	static unsigned int
dcb9eccb	580	tree_ssa_loop_done (void)
dcb9eccb	581	{
7194de72	582	free_numbers_of_iterations_estimates ();
bb445479	583	scev_finalize ();
88e6f696	584	loop_optimizer_finalize ();
2a1990e9	585	return 0;
dcb9eccb	586	}
dcb9eccb	587
0526a3ff	588	struct tree_opt_pass pass_tree_loop_done =
dcb9eccb	589	{
	590	"loopdone", /* name */
	591	NULL, /* gate */
	592	tree_ssa_loop_done, /* execute */
	593	NULL, /* sub */
	594	NULL, /* next */
	595	0, /* static_pass_number */
6a881b08	596	TV_TREE_LOOP_FINI, /* tv_id */
dcb9eccb	597	PROP_cfg, /* properties_required */
	598	0, /* properties_provided */
	599	0, /* properties_destroyed */
	600	0, /* todo_flags_start */
cbcbd868	601	TODO_cleanup_cfg \| TODO_dump_func, /* todo_flags_finish */
0f9005dd	602	0 /* letter */
dcb9eccb	603	};