[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"

/* The loop superpass.  */

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

struct gimple_opt_pass pass_tree_loop = 
{
 {
  GIMPLE_PASS,
  "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 */
 }
};

/* Loop optimizer initialization.  */

static unsigned int
tree_ssa_loop_init (void)
{
  loop_optimizer_init (LOOPS_NORMAL
		       | LOOPS_HAVE_RECORDED_EXITS);
  rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);

  if (number_of_loops () <= 1)
    return 0;

  scev_initialize ();
  return 0;
}
  
struct gimple_opt_pass pass_tree_loop_init = 
{
 {
  GIMPLE_PASS,
  "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 */
 }
};

/* 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 gimple_opt_pass pass_lim = 
{
 {
  GIMPLE_PASS,
  "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 */
 }
};

/* 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 gimple_opt_pass pass_tree_unswitch = 
{
 {
  GIMPLE_PASS,
  "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 */
 }
};

/* 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 gimple_opt_pass pass_predcom = 
{
 {
  GIMPLE_PASS,
  "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 */
 }
};

/* Loop autovectorization.  */

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

  return vectorize_loops ();
}

static bool
gate_tree_vectorize (void)
{
  return flag_tree_vectorize;
}

struct gimple_opt_pass pass_vectorize =
{
 {
  GIMPLE_PASS,
  "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 */
 }
};

/* 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 gimple_opt_pass pass_linear_transform =
{
 {
  GIMPLE_PASS,
  "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_update_ssa_only_virtuals
    | TODO_ggc_collect			/* todo_flags_finish */
 }
};

/* 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 gimple_opt_pass pass_check_data_deps =
{
 {
  GIMPLE_PASS,
  "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 */
 }
};

/* 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 gimple_opt_pass pass_iv_canon =
{
 {
  GIMPLE_PASS,
  "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 */
 }
};

/* Propagation of constants using scev.  */

static bool
gate_scev_const_prop (void)
{
  return flag_tree_scev_cprop;
}

struct gimple_opt_pass pass_scev_cprop =
{
 {
  GIMPLE_PASS,
  "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 */
 }
};

/* Remove empty loops.  */

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

  return remove_empty_loops ();
}

struct gimple_opt_pass pass_empty_loop =
{
 {
  GIMPLE_PASS,
  "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 */
 }
};

/* 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 gimple_opt_pass pass_record_bounds =
{
 {
  GIMPLE_PASS,
  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 */
 }
};

/* 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, true);
}

static bool
gate_tree_complete_unroll (void)
{
  return true;
}

struct gimple_opt_pass pass_complete_unroll =
{
 {
  GIMPLE_PASS,
  "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 */
 }
};

/* Complete unrolling of inner loops.  */

static unsigned int
tree_complete_unroll_inner (void)
{
  unsigned ret = 0;

  loop_optimizer_init (LOOPS_NORMAL
		       | LOOPS_HAVE_RECORDED_EXITS);
  if (number_of_loops () > 1)
    {
      scev_initialize ();
      ret = tree_unroll_loops_completely (optimize >= 3, false);
      free_numbers_of_iterations_estimates ();
      scev_finalize ();
    }
  loop_optimizer_finalize ();

  return ret;
}

static bool
gate_tree_complete_unroll_inner (void)
{
  return optimize >= 2;
}

struct gimple_opt_pass pass_complete_unrolli =
{
 {
  GIMPLE_PASS,
  "cunrolli",				/* name */
  gate_tree_complete_unroll_inner,	/* gate */
  tree_complete_unroll_inner,	       	/* 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 */
 }
};

/* 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 gimple_opt_pass pass_parallelize_loops =
{
 {
  GIMPLE_PASS,
  "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 */
 }
};

/* 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 gimple_opt_pass pass_loop_prefetch =
{
 {
  GIMPLE_PASS,
  "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 */
 }
};

/* 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 gimple_opt_pass pass_iv_optimize =
{
 {
  GIMPLE_PASS,
  "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 */
 }
};

/* Loop optimizer finalization.  */

static unsigned int
tree_ssa_loop_done (void)
{
  free_numbers_of_iterations_estimates ();
  scev_finalize ();
  loop_optimizer_finalize ();
  return 0;
}
  
struct gimple_opt_pass pass_tree_loop_done = 
{
 {
  GIMPLE_PASS,
  "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 */
 }
};
Commit	Line	Data
6de9cd9a	1	/* Loop optimizations over tree-ssa.
3d8864c0	2	Copyright (C) 2003, 2005, 2006, 2007 Free Software Foundation, Inc.
6de9cd9a DN	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
9dcd6f09	8	Free Software Foundation; either version 3, or (at your option) any
6de9cd9a DN	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
9dcd6f09 NC	17	along with GCC; see the file COPYING3. If not see
9dcd6f09 NC	18	<http://www.gnu.org/licenses/>. */
6de9cd9a DN	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"
6de9cd9a DN	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"
79fe1b3b	38	#include "tree-scalar-evolution.h"
6de9cd9a	39
c66b6c66 ZD	40	/* The loop superpass. */
	41
	42	static bool
9fa26457	43	gate_tree_loop (void)
c66b6c66 ZD	44	{
	45	return flag_tree_loop_optimize != 0;
	46	}
	47
8ddbbcae	48	struct gimple_opt_pass pass_tree_loop =
c66b6c66	49	{
8ddbbcae JH	50	{
8ddbbcae JH	51	GIMPLE_PASS,
c66b6c66	52	"loop", /* name */
9fa26457	53	gate_tree_loop, /* gate */
c66b6c66 ZD	54	NULL, /* execute */
	55	NULL, /* sub */
	56	NULL, /* next */
	57	0, /* static_pass_number */
	58	TV_TREE_LOOP, /* tv_id */
	59	PROP_cfg, /* properties_required */
	60	0, /* properties_provided */
	61	0, /* properties_destroyed */
	62	TODO_ggc_collect, /* todo_flags_start */
8ddbbcae JH	63	TODO_dump_func \| TODO_verify_ssa \| TODO_ggc_collect /* todo_flags_finish */
8ddbbcae JH	64	}
c66b6c66 ZD	65	};
	66
	67	/* Loop optimizer initialization. */
	68
c2924966	69	static unsigned int
c66b6c66 ZD	70	tree_ssa_loop_init (void)
c66b6c66 ZD	71	{
726a989a RB	72	loop_optimizer_init (LOOPS_NORMAL
	73	\| LOOPS_HAVE_RECORDED_EXITS);
	74	rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
	75
d51157de	76	if (number_of_loops () <= 1)
c2924966	77	return 0;
82b85a85	78
d73be268	79	scev_initialize ();
c2924966	80	return 0;
c66b6c66 ZD	81	}
c66b6c66 ZD	82
8ddbbcae	83	struct gimple_opt_pass pass_tree_loop_init =
c66b6c66	84	{
8ddbbcae JH	85	{
8ddbbcae JH	86	GIMPLE_PASS,
c66b6c66 ZD	87	"loopinit", /* name */
	88	NULL, /* gate */
	89	tree_ssa_loop_init, /* execute */
	90	NULL, /* sub */
	91	NULL, /* next */
	92	0, /* static_pass_number */
87c11134	93	TV_TREE_LOOP_INIT, /* tv_id */
c66b6c66 ZD	94	PROP_cfg, /* properties_required */
	95	0, /* properties_provided */
	96	0, /* properties_destroyed */
	97	0, /* todo_flags_start */
8ddbbcae JH	98	TODO_dump_func \| TODO_verify_loops /* todo_flags_finish */
8ddbbcae JH	99	}
c66b6c66 ZD	100	};
c66b6c66 ZD	101
a7e5372d ZD	102	/* Loop invariant motion pass. */
a7e5372d ZD	103
c2924966	104	static unsigned int
a7e5372d ZD	105	tree_ssa_loop_im (void)
a7e5372d ZD	106	{
d51157de	107	if (number_of_loops () <= 1)
c2924966	108	return 0;
a7e5372d	109
d73be268	110	tree_ssa_lim ();
c2924966	111	return 0;
a7e5372d ZD	112	}
	113
	114	static bool
	115	gate_tree_ssa_loop_im (void)
	116	{
1b08d87d	117	return flag_tree_loop_im != 0;
a7e5372d ZD	118	}
a7e5372d ZD	119
8ddbbcae	120	struct gimple_opt_pass pass_lim =
a7e5372d	121	{
8ddbbcae JH	122	{
8ddbbcae JH	123	GIMPLE_PASS,
a7e5372d ZD	124	"lim", /* name */
	125	gate_tree_ssa_loop_im, /* gate */
	126	tree_ssa_loop_im, /* execute */
	127	NULL, /* sub */
	128	NULL, /* next */
	129	0, /* static_pass_number */
	130	TV_LIM, /* tv_id */
	131	PROP_cfg, /* properties_required */
92fc4a2f ZD	132	0, /* properties_provided */
	133	0, /* properties_destroyed */
	134	0, /* todo_flags_start */
8ddbbcae JH	135	TODO_dump_func \| TODO_verify_loops /* todo_flags_finish */
8ddbbcae JH	136	}
92fc4a2f ZD	137	};
	138
	139	/* Loop unswitching pass. */
	140
c2924966	141	static unsigned int
92fc4a2f ZD	142	tree_ssa_loop_unswitch (void)
92fc4a2f ZD	143	{
d51157de	144	if (number_of_loops () <= 1)
c2924966	145	return 0;
92fc4a2f	146
d73be268	147	return tree_ssa_unswitch_loops ();
92fc4a2f ZD	148	}
	149
	150	static bool
	151	gate_tree_ssa_loop_unswitch (void)
	152	{
	153	return flag_unswitch_loops != 0;
	154	}
	155
8ddbbcae	156	struct gimple_opt_pass pass_tree_unswitch =
92fc4a2f	157	{
8ddbbcae JH	158	{
8ddbbcae JH	159	GIMPLE_PASS,
92fc4a2f ZD	160	"unswitch", /* name */
	161	gate_tree_ssa_loop_unswitch, /* gate */
	162	tree_ssa_loop_unswitch, /* execute */
	163	NULL, /* sub */
	164	NULL, /* next */
	165	0, /* static_pass_number */
	166	TV_TREE_LOOP_UNSWITCH, /* tv_id */
	167	PROP_cfg, /* properties_required */
a7e5372d ZD	168	0, /* properties_provided */
	169	0, /* properties_destroyed */
	170	0, /* todo_flags_start */
9e2f83a5	171	TODO_ggc_collect \| TODO_dump_func
8ddbbcae JH	172	\| TODO_verify_loops /* todo_flags_finish */
8ddbbcae JH	173	}
a7e5372d ZD	174	};
a7e5372d ZD	175
bbc8a8dc ZD	176	/* Predictive commoning. */
	177
	178	static unsigned
	179	run_tree_predictive_commoning (void)
	180	{
	181	if (!current_loops)
	182	return 0;
	183
	184	tree_predictive_commoning ();
	185	return 0;
	186	}
	187
	188	static bool
	189	gate_tree_predictive_commoning (void)
	190	{
	191	return flag_predictive_commoning != 0;
	192	}
	193
8ddbbcae	194	struct gimple_opt_pass pass_predcom =
bbc8a8dc	195	{
8ddbbcae JH	196	{
8ddbbcae JH	197	GIMPLE_PASS,
bbc8a8dc ZD	198	"pcom", /* name */
	199	gate_tree_predictive_commoning, /* gate */
	200	run_tree_predictive_commoning, /* execute */
	201	NULL, /* sub */
	202	NULL, /* next */
	203	0, /* static_pass_number */
	204	TV_PREDCOM, /* tv_id */
	205	PROP_cfg, /* properties_required */
	206	0, /* properties_provided */
	207	0, /* properties_destroyed */
	208	0, /* todo_flags_start */
	209	TODO_dump_func \| TODO_verify_loops
8ddbbcae JH	210	\| TODO_update_ssa_only_virtuals /* todo_flags_finish */
8ddbbcae JH	211	}
bbc8a8dc ZD	212	};
bbc8a8dc ZD	213
79fe1b3b DN	214	/* Loop autovectorization. */
79fe1b3b DN	215
c2924966	216	static unsigned int
79fe1b3b DN	217	tree_vectorize (void)
79fe1b3b DN	218	{
d6e840ee RG	219	if (number_of_loops () <= 1)
	220	return 0;
	221
d73be268	222	return vectorize_loops ();
79fe1b3b DN	223	}
	224
	225	static bool
	226	gate_tree_vectorize (void)
	227	{
d6e840ee	228	return flag_tree_vectorize;
79fe1b3b DN	229	}
79fe1b3b DN	230
8ddbbcae	231	struct gimple_opt_pass pass_vectorize =
79fe1b3b	232	{
8ddbbcae JH	233	{
8ddbbcae JH	234	GIMPLE_PASS,
79fe1b3b DN	235	"vect", /* name */
	236	gate_tree_vectorize, /* gate */
	237	tree_vectorize, /* execute */
	238	NULL, /* sub */
	239	NULL, /* next */
	240	0, /* static_pass_number */
	241	TV_TREE_VECTORIZATION, /* tv_id */
	242	PROP_cfg \| PROP_ssa, /* properties_required */
	243	0, /* properties_provided */
	244	0, /* properties_destroyed */
90ff949f	245	TODO_verify_loops, /* todo_flags_start */
9e2f83a5	246	TODO_dump_func \| TODO_update_ssa
8ddbbcae JH	247	\| TODO_ggc_collect /* todo_flags_finish */
8ddbbcae JH	248	}
79fe1b3b DN	249	};
79fe1b3b DN	250
599eabdb DB	251	/* Loop nest optimizations. */
599eabdb DB	252
c2924966	253	static unsigned int
599eabdb DB	254	tree_linear_transform (void)
599eabdb DB	255	{
d51157de	256	if (number_of_loops () <= 1)
c2924966	257	return 0;
599eabdb	258
d73be268	259	linear_transform_loops ();
c2924966	260	return 0;
599eabdb DB	261	}
	262
	263	static bool
	264	gate_tree_linear_transform (void)
	265	{
	266	return flag_tree_loop_linear != 0;
	267	}
	268
8ddbbcae	269	struct gimple_opt_pass pass_linear_transform =
599eabdb	270	{
8ddbbcae JH	271	{
8ddbbcae JH	272	GIMPLE_PASS,
599eabdb DB	273	"ltrans", /* name */
	274	gate_tree_linear_transform, /* gate */
	275	tree_linear_transform, /* execute */
	276	NULL, /* sub */
	277	NULL, /* next */
	278	0, /* static_pass_number */
	279	TV_TREE_LINEAR_TRANSFORM, /* tv_id */
	280	PROP_cfg \| PROP_ssa, /* properties_required */
	281	0, /* properties_provided */
	282	0, /* properties_destroyed */
	283	0, /* todo_flags_start */
9e2f83a5	284	TODO_dump_func \| TODO_verify_loops
1785c05d	285	\| TODO_update_ssa_only_virtuals
8ddbbcae JH	286	\| TODO_ggc_collect /* todo_flags_finish */
8ddbbcae JH	287	}
599eabdb DB	288	};
599eabdb DB	289
3d8864c0 SP	290	/* Check the correctness of the data dependence analyzers. */
	291
	292	static unsigned int
	293	check_data_deps (void)
	294	{
d51157de	295	if (number_of_loops () <= 1)
3d8864c0 SP	296	return 0;
	297
	298	tree_check_data_deps ();
	299	return 0;
	300	}
	301
	302	static bool
	303	gate_check_data_deps (void)
	304	{
	305	return flag_check_data_deps != 0;
	306	}
	307
8ddbbcae	308	struct gimple_opt_pass pass_check_data_deps =
3d8864c0	309	{
8ddbbcae JH	310	{
8ddbbcae JH	311	GIMPLE_PASS,
3d8864c0 SP	312	"ckdd", /* name */
	313	gate_check_data_deps, /* gate */
	314	check_data_deps, /* execute */
	315	NULL, /* sub */
	316	NULL, /* next */
	317	0, /* static_pass_number */
	318	TV_CHECK_DATA_DEPS, /* tv_id */
	319	PROP_cfg \| PROP_ssa, /* properties_required */
	320	0, /* properties_provided */
	321	0, /* properties_destroyed */
	322	0, /* todo_flags_start */
8ddbbcae JH	323	TODO_dump_func /* todo_flags_finish */
8ddbbcae JH	324	}
3d8864c0 SP	325	};
3d8864c0 SP	326
82b85a85 ZD	327	/* Canonical induction variable creation pass. */
82b85a85 ZD	328
c2924966	329	static unsigned int
82b85a85 ZD	330	tree_ssa_loop_ivcanon (void)
82b85a85 ZD	331	{
d51157de	332	if (number_of_loops () <= 1)
c2924966	333	return 0;
82b85a85	334
d73be268	335	return canonicalize_induction_variables ();
82b85a85 ZD	336	}
	337
	338	static bool
	339	gate_tree_ssa_loop_ivcanon (void)
	340	{
1b08d87d	341	return flag_tree_loop_ivcanon != 0;
82b85a85 ZD	342	}
82b85a85 ZD	343
8ddbbcae	344	struct gimple_opt_pass pass_iv_canon =
82b85a85	345	{
8ddbbcae JH	346	{
8ddbbcae JH	347	GIMPLE_PASS,
82b85a85 ZD	348	"ivcanon", /* name */
	349	gate_tree_ssa_loop_ivcanon, /* gate */
	350	tree_ssa_loop_ivcanon, /* execute */
	351	NULL, /* sub */
	352	NULL, /* next */
	353	0, /* static_pass_number */
	354	TV_TREE_LOOP_IVCANON, /* tv_id */
	355	PROP_cfg \| PROP_ssa, /* properties_required */
	356	0, /* properties_provided */
	357	0, /* properties_destroyed */
	358	0, /* todo_flags_start */
8ddbbcae JH	359	TODO_dump_func \| TODO_verify_loops /* todo_flags_finish */
8ddbbcae JH	360	}
684aaf29 ZD	361	};
	362
	363	/* Propagation of constants using scev. */
	364
	365	static bool
	366	gate_scev_const_prop (void)
	367	{
fbf798fc	368	return flag_tree_scev_cprop;
684aaf29 ZD	369	}
684aaf29 ZD	370
8ddbbcae	371	struct gimple_opt_pass pass_scev_cprop =
684aaf29	372	{
8ddbbcae JH	373	{
8ddbbcae JH	374	GIMPLE_PASS,
684aaf29 ZD	375	"sccp", /* name */
	376	gate_scev_const_prop, /* gate */
	377	scev_const_prop, /* execute */
	378	NULL, /* sub */
	379	NULL, /* next */
	380	0, /* static_pass_number */
	381	TV_SCEV_CONST, /* tv_id */
	382	PROP_cfg \| PROP_ssa, /* properties_required */
	383	0, /* properties_provided */
	384	0, /* properties_destroyed */
	385	0, /* todo_flags_start */
43ec2467	386	TODO_dump_func \| TODO_cleanup_cfg
8ddbbcae	387	\| TODO_update_ssa_only_virtuals
d49195a3	388	/* todo_flags_finish */
8ddbbcae	389	}
b7eae7b8 ZD	390	};
	391
	392	/* Remove empty loops. */
	393
c2924966	394	static unsigned int
b7eae7b8 ZD	395	tree_ssa_empty_loop (void)
b7eae7b8 ZD	396	{
d51157de	397	if (number_of_loops () <= 1)
c2924966	398	return 0;
b7eae7b8	399
d73be268	400	return remove_empty_loops ();
b7eae7b8 ZD	401	}
b7eae7b8 ZD	402
8ddbbcae	403	struct gimple_opt_pass pass_empty_loop =
b7eae7b8	404	{
8ddbbcae JH	405	{
8ddbbcae JH	406	GIMPLE_PASS,
b7eae7b8 ZD	407	"empty", /* name */
	408	NULL, /* gate */
	409	tree_ssa_empty_loop, /* execute */
	410	NULL, /* sub */
	411	NULL, /* next */
	412	0, /* static_pass_number */
	413	TV_COMPLETE_UNROLL, /* tv_id */
	414	PROP_cfg \| PROP_ssa, /* properties_required */
	415	0, /* properties_provided */
	416	0, /* properties_destroyed */
	417	0, /* todo_flags_start */
9e2f83a5	418	TODO_dump_func \| TODO_verify_loops
8ddbbcae JH	419	\| TODO_ggc_collect /* todo_flags_finish */
8ddbbcae JH	420	}
82b85a85 ZD	421	};
82b85a85 ZD	422
f3cd574f ZD	423	/* Record bounds on numbers of iterations of loops. */
f3cd574f ZD	424
c2924966	425	static unsigned int
f3cd574f ZD	426	tree_ssa_loop_bounds (void)
f3cd574f ZD	427	{
d51157de	428	if (number_of_loops () <= 1)
c2924966	429	return 0;
f3cd574f	430
d73be268	431	estimate_numbers_of_iterations ();
f3cd574f	432	scev_reset ();
c2924966	433	return 0;
f3cd574f ZD	434	}
f3cd574f ZD	435
8ddbbcae	436	struct gimple_opt_pass pass_record_bounds =
f3cd574f	437	{
8ddbbcae JH	438	{
8ddbbcae JH	439	GIMPLE_PASS,
81842e1b	440	NULL, /* name */
f3cd574f ZD	441	NULL, /* gate */
	442	tree_ssa_loop_bounds, /* execute */
	443	NULL, /* sub */
	444	NULL, /* next */
	445	0, /* static_pass_number */
ccbdbf0a	446	TV_TREE_LOOP_BOUNDS, /* tv_id */
f3cd574f ZD	447	PROP_cfg \| PROP_ssa, /* properties_required */
	448	0, /* properties_provided */
	449	0, /* properties_destroyed */
	450	0, /* todo_flags_start */
8ddbbcae JH	451	0 /* todo_flags_finish */
8ddbbcae JH	452	}
f3cd574f ZD	453	};
f3cd574f ZD	454
82b85a85 ZD	455	/* Complete unrolling of loops. */
82b85a85 ZD	456
c2924966	457	static unsigned int
82b85a85 ZD	458	tree_complete_unroll (void)
82b85a85 ZD	459	{
d51157de	460	if (number_of_loops () <= 1)
c2924966	461	return 0;
82b85a85	462
d73be268 ZD	463	return tree_unroll_loops_completely (flag_unroll_loops
d73be268 ZD	464	\|\| flag_peel_loops
d6e840ee	465	\|\| optimize >= 3, true);
82b85a85 ZD	466	}
	467
	468	static bool
	469	gate_tree_complete_unroll (void)
	470	{
91a01f21	471	return true;
82b85a85 ZD	472	}
82b85a85 ZD	473
8ddbbcae	474	struct gimple_opt_pass pass_complete_unroll =
82b85a85	475	{
8ddbbcae JH	476	{
8ddbbcae JH	477	GIMPLE_PASS,
82b85a85 ZD	478	"cunroll", /* name */
	479	gate_tree_complete_unroll, /* gate */
	480	tree_complete_unroll, /* execute */
	481	NULL, /* sub */
	482	NULL, /* next */
	483	0, /* static_pass_number */
	484	TV_COMPLETE_UNROLL, /* tv_id */
	485	PROP_cfg \| PROP_ssa, /* properties_required */
8b11a64c ZD	486	0, /* properties_provided */
	487	0, /* properties_destroyed */
	488	0, /* todo_flags_start */
9e2f83a5	489	TODO_dump_func \| TODO_verify_loops
8ddbbcae JH	490	\| TODO_ggc_collect /* todo_flags_finish */
8ddbbcae JH	491	}
8b11a64c ZD	492	};
8b11a64c ZD	493
d6e840ee RG	494	/* Complete unrolling of inner loops. */
	495
	496	static unsigned int
	497	tree_complete_unroll_inner (void)
	498	{
	499	unsigned ret = 0;
	500
	501	loop_optimizer_init (LOOPS_NORMAL
	502	\| LOOPS_HAVE_RECORDED_EXITS);
	503	if (number_of_loops () > 1)
	504	{
	505	scev_initialize ();
	506	ret = tree_unroll_loops_completely (optimize >= 3, false);
	507	free_numbers_of_iterations_estimates ();
	508	scev_finalize ();
	509	}
	510	loop_optimizer_finalize ();
	511
	512	return ret;
	513	}
	514
	515	static bool
	516	gate_tree_complete_unroll_inner (void)
	517	{
	518	return optimize >= 2;
	519	}
	520
	521	struct gimple_opt_pass pass_complete_unrolli =
	522	{
	523	{
	524	GIMPLE_PASS,
	525	"cunrolli", /* name */
	526	gate_tree_complete_unroll_inner, /* gate */
	527	tree_complete_unroll_inner, /* execute */
	528	NULL, /* sub */
	529	NULL, /* next */
	530	0, /* static_pass_number */
	531	TV_COMPLETE_UNROLL, /* tv_id */
	532	PROP_cfg \| PROP_ssa, /* properties_required */
	533	0, /* properties_provided */
	534	0, /* properties_destroyed */
	535	0, /* todo_flags_start */
	536	TODO_dump_func \| TODO_verify_loops
	537	\| TODO_ggc_collect /* todo_flags_finish */
	538	}
	539	};
	540
5f40b3cb ZD	541	/* Parallelization. */
	542
	543	static bool
	544	gate_tree_parallelize_loops (void)
	545	{
4e9012fd	546	return flag_tree_parallelize_loops > 1;
5f40b3cb ZD	547	}
	548
	549	static unsigned
	550	tree_parallelize_loops (void)
	551	{
	552	if (number_of_loops () <= 1)
	553	return 0;
	554
	555	if (parallelize_loops ())
	556	return TODO_cleanup_cfg \| TODO_rebuild_alias;
	557	return 0;
	558	}
	559
8ddbbcae	560	struct gimple_opt_pass pass_parallelize_loops =
5f40b3cb	561	{
8ddbbcae JH	562	{
8ddbbcae JH	563	GIMPLE_PASS,
5f40b3cb ZD	564	"parloops", /* name */
	565	gate_tree_parallelize_loops, /* gate */
	566	tree_parallelize_loops, /* execute */
	567	NULL, /* sub */
	568	NULL, /* next */
	569	0, /* static_pass_number */
	570	TV_TREE_PARALLELIZE_LOOPS, /* tv_id */
	571	PROP_cfg \| PROP_ssa, /* properties_required */
	572	0, /* properties_provided */
	573	0, /* properties_destroyed */
	574	0, /* todo_flags_start */
8ddbbcae JH	575	TODO_dump_func \| TODO_verify_loops /* todo_flags_finish */
8ddbbcae JH	576	}
5f40b3cb ZD	577	};
5f40b3cb ZD	578
17684618 ZD	579	/* Prefetching. */
17684618 ZD	580
c2924966	581	static unsigned int
17684618 ZD	582	tree_ssa_loop_prefetch (void)
17684618 ZD	583	{
d51157de	584	if (number_of_loops () <= 1)
c2924966	585	return 0;
17684618	586
d73be268	587	return tree_ssa_prefetch_arrays ();
17684618 ZD	588	}
	589
	590	static bool
	591	gate_tree_ssa_loop_prefetch (void)
	592	{
efa1cdf0	593	return flag_prefetch_loop_arrays != 0;
17684618 ZD	594	}
17684618 ZD	595
8ddbbcae	596	struct gimple_opt_pass pass_loop_prefetch =
17684618	597	{
8ddbbcae JH	598	{
8ddbbcae JH	599	GIMPLE_PASS,
e324a72f	600	"aprefetch", /* name */
17684618 ZD	601	gate_tree_ssa_loop_prefetch, /* gate */
	602	tree_ssa_loop_prefetch, /* execute */
	603	NULL, /* sub */
	604	NULL, /* next */
	605	0, /* static_pass_number */
	606	TV_TREE_PREFETCH, /* tv_id */
	607	PROP_cfg \| PROP_ssa, /* properties_required */
	608	0, /* properties_provided */
	609	0, /* properties_destroyed */
	610	0, /* todo_flags_start */
8ddbbcae JH	611	TODO_dump_func \| TODO_verify_loops /* todo_flags_finish */
8ddbbcae JH	612	}
17684618 ZD	613	};
17684618 ZD	614
8b11a64c ZD	615	/* Induction variable optimizations. */
8b11a64c ZD	616
c2924966	617	static unsigned int
8b11a64c ZD	618	tree_ssa_loop_ivopts (void)
8b11a64c ZD	619	{
d51157de	620	if (number_of_loops () <= 1)
c2924966	621	return 0;
8b11a64c	622
d73be268	623	tree_ssa_iv_optimize ();
c2924966	624	return 0;
8b11a64c ZD	625	}
	626
	627	static bool
	628	gate_tree_ssa_loop_ivopts (void)
	629	{
	630	return flag_ivopts != 0;
	631	}
	632
8ddbbcae	633	struct gimple_opt_pass pass_iv_optimize =
8b11a64c	634	{
8ddbbcae JH	635	{
8ddbbcae JH	636	GIMPLE_PASS,
8b11a64c ZD	637	"ivopts", /* name */
	638	gate_tree_ssa_loop_ivopts, /* gate */
	639	tree_ssa_loop_ivopts, /* execute */
	640	NULL, /* sub */
	641	NULL, /* next */
	642	0, /* static_pass_number */
	643	TV_TREE_LOOP_IVOPTS, /* tv_id */
	644	PROP_cfg \| PROP_ssa, /* properties_required */
82b85a85 ZD	645	0, /* properties_provided */
	646	0, /* properties_destroyed */
	647	0, /* todo_flags_start */
9e2f83a5	648	TODO_dump_func \| TODO_verify_loops
8ddbbcae JH	649	\| TODO_update_ssa \| TODO_ggc_collect /* todo_flags_finish */
8ddbbcae JH	650	}
82b85a85 ZD	651	};
82b85a85 ZD	652
c66b6c66 ZD	653	/* Loop optimizer finalization. */
c66b6c66 ZD	654
c2924966	655	static unsigned int
c66b6c66 ZD	656	tree_ssa_loop_done (void)
c66b6c66 ZD	657	{
d73be268	658	free_numbers_of_iterations_estimates ();
82b85a85	659	scev_finalize ();
598ec7bd	660	loop_optimizer_finalize ();
c2924966	661	return 0;
c66b6c66 ZD	662	}
c66b6c66 ZD	663
8ddbbcae	664	struct gimple_opt_pass pass_tree_loop_done =
c66b6c66	665	{
8ddbbcae JH	666	{
8ddbbcae JH	667	GIMPLE_PASS,
c66b6c66 ZD	668	"loopdone", /* name */
	669	NULL, /* gate */
	670	tree_ssa_loop_done, /* execute */
	671	NULL, /* sub */
	672	NULL, /* next */
	673	0, /* static_pass_number */
87c11134	674	TV_TREE_LOOP_FINI, /* tv_id */
c66b6c66 ZD	675	PROP_cfg, /* properties_required */
	676	0, /* properties_provided */
	677	0, /* properties_destroyed */
	678	0, /* todo_flags_start */
8ddbbcae JH	679	TODO_cleanup_cfg \| TODO_dump_func /* todo_flags_finish */
8ddbbcae JH	680	}
c66b6c66	681	};