[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 */
 }
};

/* GRAPHITE optimizations.  */

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

  graphite_transform_loops ();

  return 0;
}

static bool
gate_graphite_transforms (void)
{
  /* Enable -fgraphite pass if any one of the graphite optimization flags 
     is turned on.  */
  if (flag_loop_block || flag_loop_interchange || flag_loop_strip_mine
      || flag_graphite_identity)
    flag_graphite = 1;

  return flag_graphite != 0;
}

struct gimple_opt_pass pass_graphite_transforms =
{
 {
  GIMPLE_PASS,
  "graphite",				/* name */
  gate_graphite_transforms,		/* gate */
  graphite_transforms,       		/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_GRAPHITE_TRANSFORMS,  		/* tv_id */
  PROP_cfg | PROP_ssa,			/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  TODO_verify_loops			/* 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
f8bf9252 SP	290	/* GRAPHITE optimizations. */
	291
	292	static unsigned int
	293	graphite_transforms (void)
	294	{
	295	if (!current_loops)
	296	return 0;
	297
	298	graphite_transform_loops ();
	299
	300	return 0;
	301	}
	302
	303	static bool
	304	gate_graphite_transforms (void)
	305	{
	306	/* Enable -fgraphite pass if any one of the graphite optimization flags
	307	is turned on. */
20ed8b32 TG	308	if (flag_loop_block \|\| flag_loop_interchange \|\| flag_loop_strip_mine
20ed8b32 TG	309	\|\| flag_graphite_identity)
f8bf9252 SP	310	flag_graphite = 1;
	311
	312	return flag_graphite != 0;
	313	}
	314
	315	struct gimple_opt_pass pass_graphite_transforms =
	316	{
	317	{
	318	GIMPLE_PASS,
	319	"graphite", /* name */
	320	gate_graphite_transforms, /* gate */
	321	graphite_transforms, /* execute */
	322	NULL, /* sub */
	323	NULL, /* next */
	324	0, /* static_pass_number */
	325	TV_GRAPHITE_TRANSFORMS, /* tv_id */
	326	PROP_cfg \| PROP_ssa, /* properties_required */
	327	0, /* properties_provided */
	328	0, /* properties_destroyed */
	329	0, /* todo_flags_start */
	330	TODO_verify_loops /* todo_flags_finish */
	331	}
	332	};
	333
3d8864c0 SP	334	/* Check the correctness of the data dependence analyzers. */
	335
	336	static unsigned int
	337	check_data_deps (void)
	338	{
d51157de	339	if (number_of_loops () <= 1)
3d8864c0 SP	340	return 0;
	341
	342	tree_check_data_deps ();
	343	return 0;
	344	}
	345
	346	static bool
	347	gate_check_data_deps (void)
	348	{
	349	return flag_check_data_deps != 0;
	350	}
	351
8ddbbcae	352	struct gimple_opt_pass pass_check_data_deps =
3d8864c0	353	{
8ddbbcae JH	354	{
8ddbbcae JH	355	GIMPLE_PASS,
3d8864c0 SP	356	"ckdd", /* name */
	357	gate_check_data_deps, /* gate */
	358	check_data_deps, /* execute */
	359	NULL, /* sub */
	360	NULL, /* next */
	361	0, /* static_pass_number */
	362	TV_CHECK_DATA_DEPS, /* tv_id */
	363	PROP_cfg \| PROP_ssa, /* properties_required */
	364	0, /* properties_provided */
	365	0, /* properties_destroyed */
	366	0, /* todo_flags_start */
8ddbbcae JH	367	TODO_dump_func /* todo_flags_finish */
8ddbbcae JH	368	}
3d8864c0 SP	369	};
3d8864c0 SP	370
82b85a85 ZD	371	/* Canonical induction variable creation pass. */
82b85a85 ZD	372
c2924966	373	static unsigned int
82b85a85 ZD	374	tree_ssa_loop_ivcanon (void)
82b85a85 ZD	375	{
d51157de	376	if (number_of_loops () <= 1)
c2924966	377	return 0;
82b85a85	378
d73be268	379	return canonicalize_induction_variables ();
82b85a85 ZD	380	}
	381
	382	static bool
	383	gate_tree_ssa_loop_ivcanon (void)
	384	{
1b08d87d	385	return flag_tree_loop_ivcanon != 0;
82b85a85 ZD	386	}
82b85a85 ZD	387
8ddbbcae	388	struct gimple_opt_pass pass_iv_canon =
82b85a85	389	{
8ddbbcae JH	390	{
8ddbbcae JH	391	GIMPLE_PASS,
82b85a85 ZD	392	"ivcanon", /* name */
	393	gate_tree_ssa_loop_ivcanon, /* gate */
	394	tree_ssa_loop_ivcanon, /* execute */
	395	NULL, /* sub */
	396	NULL, /* next */
	397	0, /* static_pass_number */
	398	TV_TREE_LOOP_IVCANON, /* tv_id */
	399	PROP_cfg \| PROP_ssa, /* properties_required */
	400	0, /* properties_provided */
	401	0, /* properties_destroyed */
	402	0, /* todo_flags_start */
8ddbbcae JH	403	TODO_dump_func \| TODO_verify_loops /* todo_flags_finish */
8ddbbcae JH	404	}
684aaf29 ZD	405	};
	406
	407	/* Propagation of constants using scev. */
	408
	409	static bool
	410	gate_scev_const_prop (void)
	411	{
fbf798fc	412	return flag_tree_scev_cprop;
684aaf29 ZD	413	}
684aaf29 ZD	414
8ddbbcae	415	struct gimple_opt_pass pass_scev_cprop =
684aaf29	416	{
8ddbbcae JH	417	{
8ddbbcae JH	418	GIMPLE_PASS,
684aaf29 ZD	419	"sccp", /* name */
	420	gate_scev_const_prop, /* gate */
	421	scev_const_prop, /* execute */
	422	NULL, /* sub */
	423	NULL, /* next */
	424	0, /* static_pass_number */
	425	TV_SCEV_CONST, /* tv_id */
	426	PROP_cfg \| PROP_ssa, /* properties_required */
	427	0, /* properties_provided */
	428	0, /* properties_destroyed */
	429	0, /* todo_flags_start */
43ec2467	430	TODO_dump_func \| TODO_cleanup_cfg
8ddbbcae	431	\| TODO_update_ssa_only_virtuals
d49195a3	432	/* todo_flags_finish */
8ddbbcae	433	}
b7eae7b8 ZD	434	};
	435
	436	/* Remove empty loops. */
	437
c2924966	438	static unsigned int
b7eae7b8 ZD	439	tree_ssa_empty_loop (void)
b7eae7b8 ZD	440	{
d51157de	441	if (number_of_loops () <= 1)
c2924966	442	return 0;
b7eae7b8	443
d73be268	444	return remove_empty_loops ();
b7eae7b8 ZD	445	}
b7eae7b8 ZD	446
8ddbbcae	447	struct gimple_opt_pass pass_empty_loop =
b7eae7b8	448	{
8ddbbcae JH	449	{
8ddbbcae JH	450	GIMPLE_PASS,
b7eae7b8 ZD	451	"empty", /* name */
	452	NULL, /* gate */
	453	tree_ssa_empty_loop, /* execute */
	454	NULL, /* sub */
	455	NULL, /* next */
	456	0, /* static_pass_number */
	457	TV_COMPLETE_UNROLL, /* tv_id */
	458	PROP_cfg \| PROP_ssa, /* properties_required */
	459	0, /* properties_provided */
	460	0, /* properties_destroyed */
	461	0, /* todo_flags_start */
9e2f83a5	462	TODO_dump_func \| TODO_verify_loops
8ddbbcae JH	463	\| TODO_ggc_collect /* todo_flags_finish */
8ddbbcae JH	464	}
82b85a85 ZD	465	};
82b85a85 ZD	466
f3cd574f ZD	467	/* Record bounds on numbers of iterations of loops. */
f3cd574f ZD	468
c2924966	469	static unsigned int
f3cd574f ZD	470	tree_ssa_loop_bounds (void)
f3cd574f ZD	471	{
d51157de	472	if (number_of_loops () <= 1)
c2924966	473	return 0;
f3cd574f	474
d73be268	475	estimate_numbers_of_iterations ();
f3cd574f	476	scev_reset ();
c2924966	477	return 0;
f3cd574f ZD	478	}
f3cd574f ZD	479
8ddbbcae	480	struct gimple_opt_pass pass_record_bounds =
f3cd574f	481	{
8ddbbcae JH	482	{
8ddbbcae JH	483	GIMPLE_PASS,
81842e1b	484	NULL, /* name */
f3cd574f ZD	485	NULL, /* gate */
	486	tree_ssa_loop_bounds, /* execute */
	487	NULL, /* sub */
	488	NULL, /* next */
	489	0, /* static_pass_number */
ccbdbf0a	490	TV_TREE_LOOP_BOUNDS, /* tv_id */
f3cd574f ZD	491	PROP_cfg \| PROP_ssa, /* properties_required */
	492	0, /* properties_provided */
	493	0, /* properties_destroyed */
	494	0, /* todo_flags_start */
8ddbbcae JH	495	0 /* todo_flags_finish */
8ddbbcae JH	496	}
f3cd574f ZD	497	};
f3cd574f ZD	498
82b85a85 ZD	499	/* Complete unrolling of loops. */
82b85a85 ZD	500
c2924966	501	static unsigned int
82b85a85 ZD	502	tree_complete_unroll (void)
82b85a85 ZD	503	{
d51157de	504	if (number_of_loops () <= 1)
c2924966	505	return 0;
82b85a85	506
d73be268 ZD	507	return tree_unroll_loops_completely (flag_unroll_loops
d73be268 ZD	508	\|\| flag_peel_loops
d6e840ee	509	\|\| optimize >= 3, true);
82b85a85 ZD	510	}
	511
	512	static bool
	513	gate_tree_complete_unroll (void)
	514	{
91a01f21	515	return true;
82b85a85 ZD	516	}
82b85a85 ZD	517
8ddbbcae	518	struct gimple_opt_pass pass_complete_unroll =
82b85a85	519	{
8ddbbcae JH	520	{
8ddbbcae JH	521	GIMPLE_PASS,
82b85a85 ZD	522	"cunroll", /* name */
	523	gate_tree_complete_unroll, /* gate */
	524	tree_complete_unroll, /* execute */
	525	NULL, /* sub */
	526	NULL, /* next */
	527	0, /* static_pass_number */
	528	TV_COMPLETE_UNROLL, /* tv_id */
	529	PROP_cfg \| PROP_ssa, /* properties_required */
8b11a64c ZD	530	0, /* properties_provided */
	531	0, /* properties_destroyed */
	532	0, /* todo_flags_start */
9e2f83a5	533	TODO_dump_func \| TODO_verify_loops
8ddbbcae JH	534	\| TODO_ggc_collect /* todo_flags_finish */
8ddbbcae JH	535	}
8b11a64c ZD	536	};
8b11a64c ZD	537
d6e840ee RG	538	/* Complete unrolling of inner loops. */
	539
	540	static unsigned int
	541	tree_complete_unroll_inner (void)
	542	{
	543	unsigned ret = 0;
	544
	545	loop_optimizer_init (LOOPS_NORMAL
	546	\| LOOPS_HAVE_RECORDED_EXITS);
	547	if (number_of_loops () > 1)
	548	{
	549	scev_initialize ();
	550	ret = tree_unroll_loops_completely (optimize >= 3, false);
	551	free_numbers_of_iterations_estimates ();
	552	scev_finalize ();
	553	}
	554	loop_optimizer_finalize ();
	555
	556	return ret;
	557	}
	558
	559	static bool
	560	gate_tree_complete_unroll_inner (void)
	561	{
	562	return optimize >= 2;
	563	}
	564
	565	struct gimple_opt_pass pass_complete_unrolli =
	566	{
	567	{
	568	GIMPLE_PASS,
	569	"cunrolli", /* name */
	570	gate_tree_complete_unroll_inner, /* gate */
	571	tree_complete_unroll_inner, /* execute */
	572	NULL, /* sub */
	573	NULL, /* next */
	574	0, /* static_pass_number */
	575	TV_COMPLETE_UNROLL, /* tv_id */
	576	PROP_cfg \| PROP_ssa, /* properties_required */
	577	0, /* properties_provided */
	578	0, /* properties_destroyed */
	579	0, /* todo_flags_start */
	580	TODO_dump_func \| TODO_verify_loops
	581	\| TODO_ggc_collect /* todo_flags_finish */
	582	}
	583	};
	584
5f40b3cb ZD	585	/* Parallelization. */
	586
	587	static bool
	588	gate_tree_parallelize_loops (void)
	589	{
4e9012fd	590	return flag_tree_parallelize_loops > 1;
5f40b3cb ZD	591	}
	592
	593	static unsigned
	594	tree_parallelize_loops (void)
	595	{
	596	if (number_of_loops () <= 1)
	597	return 0;
	598
	599	if (parallelize_loops ())
	600	return TODO_cleanup_cfg \| TODO_rebuild_alias;
	601	return 0;
	602	}
	603
8ddbbcae	604	struct gimple_opt_pass pass_parallelize_loops =
5f40b3cb	605	{
8ddbbcae JH	606	{
8ddbbcae JH	607	GIMPLE_PASS,
5f40b3cb ZD	608	"parloops", /* name */
	609	gate_tree_parallelize_loops, /* gate */
	610	tree_parallelize_loops, /* execute */
	611	NULL, /* sub */
	612	NULL, /* next */
	613	0, /* static_pass_number */
	614	TV_TREE_PARALLELIZE_LOOPS, /* tv_id */
	615	PROP_cfg \| PROP_ssa, /* properties_required */
	616	0, /* properties_provided */
	617	0, /* properties_destroyed */
	618	0, /* todo_flags_start */
8ddbbcae JH	619	TODO_dump_func \| TODO_verify_loops /* todo_flags_finish */
8ddbbcae JH	620	}
5f40b3cb ZD	621	};
5f40b3cb ZD	622
17684618 ZD	623	/* Prefetching. */
17684618 ZD	624
c2924966	625	static unsigned int
17684618 ZD	626	tree_ssa_loop_prefetch (void)
17684618 ZD	627	{
d51157de	628	if (number_of_loops () <= 1)
c2924966	629	return 0;
17684618	630
d73be268	631	return tree_ssa_prefetch_arrays ();
17684618 ZD	632	}
	633
	634	static bool
	635	gate_tree_ssa_loop_prefetch (void)
	636	{
efa1cdf0	637	return flag_prefetch_loop_arrays != 0;
17684618 ZD	638	}
17684618 ZD	639
8ddbbcae	640	struct gimple_opt_pass pass_loop_prefetch =
17684618	641	{
8ddbbcae JH	642	{
8ddbbcae JH	643	GIMPLE_PASS,
e324a72f	644	"aprefetch", /* name */
17684618 ZD	645	gate_tree_ssa_loop_prefetch, /* gate */
	646	tree_ssa_loop_prefetch, /* execute */
	647	NULL, /* sub */
	648	NULL, /* next */
	649	0, /* static_pass_number */
	650	TV_TREE_PREFETCH, /* tv_id */
	651	PROP_cfg \| PROP_ssa, /* properties_required */
	652	0, /* properties_provided */
	653	0, /* properties_destroyed */
	654	0, /* todo_flags_start */
8ddbbcae JH	655	TODO_dump_func \| TODO_verify_loops /* todo_flags_finish */
8ddbbcae JH	656	}
17684618 ZD	657	};
17684618 ZD	658
8b11a64c ZD	659	/* Induction variable optimizations. */
8b11a64c ZD	660
c2924966	661	static unsigned int
8b11a64c ZD	662	tree_ssa_loop_ivopts (void)
8b11a64c ZD	663	{
d51157de	664	if (number_of_loops () <= 1)
c2924966	665	return 0;
8b11a64c	666
d73be268	667	tree_ssa_iv_optimize ();
c2924966	668	return 0;
8b11a64c ZD	669	}
	670
	671	static bool
	672	gate_tree_ssa_loop_ivopts (void)
	673	{
	674	return flag_ivopts != 0;
	675	}
	676
8ddbbcae	677	struct gimple_opt_pass pass_iv_optimize =
8b11a64c	678	{
8ddbbcae JH	679	{
8ddbbcae JH	680	GIMPLE_PASS,
8b11a64c ZD	681	"ivopts", /* name */
	682	gate_tree_ssa_loop_ivopts, /* gate */
	683	tree_ssa_loop_ivopts, /* execute */
	684	NULL, /* sub */
	685	NULL, /* next */
	686	0, /* static_pass_number */
	687	TV_TREE_LOOP_IVOPTS, /* tv_id */
	688	PROP_cfg \| PROP_ssa, /* properties_required */
82b85a85 ZD	689	0, /* properties_provided */
	690	0, /* properties_destroyed */
	691	0, /* todo_flags_start */
9e2f83a5	692	TODO_dump_func \| TODO_verify_loops
8ddbbcae JH	693	\| TODO_update_ssa \| TODO_ggc_collect /* todo_flags_finish */
8ddbbcae JH	694	}
82b85a85 ZD	695	};
82b85a85 ZD	696
c66b6c66 ZD	697	/* Loop optimizer finalization. */
c66b6c66 ZD	698
c2924966	699	static unsigned int
c66b6c66 ZD	700	tree_ssa_loop_done (void)
c66b6c66 ZD	701	{
d73be268	702	free_numbers_of_iterations_estimates ();
82b85a85	703	scev_finalize ();
598ec7bd	704	loop_optimizer_finalize ();
c2924966	705	return 0;
c66b6c66 ZD	706	}
c66b6c66 ZD	707
8ddbbcae	708	struct gimple_opt_pass pass_tree_loop_done =
c66b6c66	709	{
8ddbbcae JH	710	{
8ddbbcae JH	711	GIMPLE_PASS,
c66b6c66 ZD	712	"loopdone", /* name */
	713	NULL, /* gate */
	714	tree_ssa_loop_done, /* execute */
	715	NULL, /* sub */
	716	NULL, /* next */
	717	0, /* static_pass_number */
87c11134	718	TV_TREE_LOOP_FINI, /* tv_id */
c66b6c66 ZD	719	PROP_cfg, /* properties_required */
	720	0, /* properties_provided */
	721	0, /* properties_destroyed */
	722	0, /* todo_flags_start */
8ddbbcae JH	723	TODO_cleanup_cfg \| TODO_dump_func /* todo_flags_finish */
8ddbbcae JH	724	}
c66b6c66	725	};