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

/* Loop optimizations over tree-ssa.
   Copyright (C) 2003, 2005, 2006, 2007, 2008 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 "tm_p.h"
#include "basic-block.h"
#include "output.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"
#include "diagnostic-core.h"
#include "toplev.h"
#include "tree-vectorizer.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_flags_finish */
 }
};

/* Loop invariant motion pass.  */

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

  return tree_ssa_lim ();
}

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_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_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_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 */
  0,					/* 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_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_loop_parallelize_all
      || flag_loop_flatten)
    flag_graphite = 1;

  return flag_graphite != 0;
}

struct gimple_opt_pass pass_graphite =
{
 {
  GIMPLE_PASS,
  "graphite0",				/* name */
  gate_graphite_transforms,		/* gate */
  NULL,					/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_GRAPHITE,				/* tv_id */
  PROP_cfg | PROP_ssa,			/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  0					/* todo_flags_finish */
 }
};

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

/* 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 (true);
  scev_reset ();
  return 0;
}

struct gimple_opt_pass pass_record_bounds =
{
 {
  GIMPLE_PASS,
  "*record_bounds",			/* 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_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_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_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_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_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.
66647d44	2	Copyright (C) 2003, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
b8698a0f	3
6de9cd9a	4	This file is part of GCC.
b8698a0f	5
6de9cd9a DN	6	GCC is free software; you can redistribute it and/or modify it
6de9cd9a DN	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	9	later version.
b8698a0f	10
6de9cd9a DN	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.
b8698a0f	15
6de9cd9a	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"
6de9cd9a	25	#include "tm_p.h"
6de9cd9a DN	26	#include "basic-block.h"
6de9cd9a DN	27	#include "output.h"
6de9cd9a DN	28	#include "tree-flow.h"
	29	#include "tree-dump.h"
	30	#include "tree-pass.h"
	31	#include "timevar.h"
	32	#include "cfgloop.h"
	33	#include "flags.h"
	34	#include "tree-inline.h"
79fe1b3b	35	#include "tree-scalar-evolution.h"
718f9c0f	36	#include "diagnostic-core.h"
204b560f	37	#include "toplev.h"
8ed77e22	38	#include "tree-vectorizer.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
b8698a0f	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	81	}
b8698a0f L	82
b8698a0f L	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 */
98b6e9dd	98	TODO_dump_func /* todo_flags_finish */
8ddbbcae	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
e3bdfed6	110	return tree_ssa_lim ();
a7e5372d ZD	111	}
	112
	113	static bool
	114	gate_tree_ssa_loop_im (void)
	115	{
1b08d87d	116	return flag_tree_loop_im != 0;
a7e5372d ZD	117	}
a7e5372d ZD	118
b8698a0f	119	struct gimple_opt_pass pass_lim =
a7e5372d	120	{
8ddbbcae JH	121	{
8ddbbcae JH	122	GIMPLE_PASS,
a7e5372d ZD	123	"lim", /* name */
	124	gate_tree_ssa_loop_im, /* gate */
	125	tree_ssa_loop_im, /* execute */
	126	NULL, /* sub */
	127	NULL, /* next */
	128	0, /* static_pass_number */
	129	TV_LIM, /* tv_id */
	130	PROP_cfg, /* properties_required */
92fc4a2f ZD	131	0, /* properties_provided */
	132	0, /* properties_destroyed */
	133	0, /* todo_flags_start */
98b6e9dd	134	TODO_dump_func /* todo_flags_finish */
8ddbbcae	135	}
92fc4a2f ZD	136	};
	137
	138	/* Loop unswitching pass. */
	139
c2924966	140	static unsigned int
92fc4a2f ZD	141	tree_ssa_loop_unswitch (void)
92fc4a2f ZD	142	{
d51157de	143	if (number_of_loops () <= 1)
c2924966	144	return 0;
92fc4a2f	145
d73be268	146	return tree_ssa_unswitch_loops ();
92fc4a2f ZD	147	}
	148
	149	static bool
	150	gate_tree_ssa_loop_unswitch (void)
	151	{
	152	return flag_unswitch_loops != 0;
	153	}
	154
b8698a0f	155	struct gimple_opt_pass pass_tree_unswitch =
92fc4a2f	156	{
8ddbbcae JH	157	{
8ddbbcae JH	158	GIMPLE_PASS,
92fc4a2f ZD	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 */
a7e5372d ZD	167	0, /* properties_provided */
	168	0, /* properties_destroyed */
	169	0, /* todo_flags_start */
98b6e9dd	170	TODO_ggc_collect \| TODO_dump_func /* todo_flags_finish */
8ddbbcae	171	}
a7e5372d ZD	172	};
a7e5372d ZD	173
bbc8a8dc ZD	174	/* Predictive commoning. */
	175
	176	static unsigned
	177	run_tree_predictive_commoning (void)
	178	{
	179	if (!current_loops)
	180	return 0;
	181
	182	tree_predictive_commoning ();
	183	return 0;
	184	}
	185
	186	static bool
	187	gate_tree_predictive_commoning (void)
	188	{
	189	return flag_predictive_commoning != 0;
	190	}
	191
b8698a0f	192	struct gimple_opt_pass pass_predcom =
bbc8a8dc	193	{
8ddbbcae JH	194	{
8ddbbcae JH	195	GIMPLE_PASS,
bbc8a8dc ZD	196	"pcom", /* name */
	197	gate_tree_predictive_commoning, /* gate */
	198	run_tree_predictive_commoning, /* execute */
	199	NULL, /* sub */
	200	NULL, /* next */
	201	0, /* static_pass_number */
	202	TV_PREDCOM, /* tv_id */
	203	PROP_cfg, /* properties_required */
	204	0, /* properties_provided */
	205	0, /* properties_destroyed */
	206	0, /* todo_flags_start */
98b6e9dd	207	TODO_dump_func
8ddbbcae JH	208	\| TODO_update_ssa_only_virtuals /* todo_flags_finish */
8ddbbcae JH	209	}
bbc8a8dc ZD	210	};
bbc8a8dc ZD	211
79fe1b3b DN	212	/* Loop autovectorization. */
79fe1b3b DN	213
c2924966	214	static unsigned int
79fe1b3b DN	215	tree_vectorize (void)
79fe1b3b DN	216	{
d6e840ee RG	217	if (number_of_loops () <= 1)
	218	return 0;
	219
d73be268	220	return vectorize_loops ();
79fe1b3b DN	221	}
	222
	223	static bool
	224	gate_tree_vectorize (void)
	225	{
d6e840ee	226	return flag_tree_vectorize;
79fe1b3b DN	227	}
79fe1b3b DN	228
8ddbbcae	229	struct gimple_opt_pass pass_vectorize =
79fe1b3b	230	{
8ddbbcae JH	231	{
8ddbbcae JH	232	GIMPLE_PASS,
79fe1b3b DN	233	"vect", /* name */
	234	gate_tree_vectorize, /* gate */
	235	tree_vectorize, /* execute */
	236	NULL, /* sub */
	237	NULL, /* next */
	238	0, /* static_pass_number */
	239	TV_TREE_VECTORIZATION, /* tv_id */
	240	PROP_cfg \| PROP_ssa, /* properties_required */
	241	0, /* properties_provided */
	242	0, /* properties_destroyed */
98b6e9dd	243	0, /* todo_flags_start */
9e2f83a5	244	TODO_dump_func \| TODO_update_ssa
8ddbbcae JH	245	\| TODO_ggc_collect /* todo_flags_finish */
8ddbbcae JH	246	}
79fe1b3b DN	247	};
79fe1b3b DN	248
599eabdb DB	249	/* Loop nest optimizations. */
599eabdb DB	250
c2924966	251	static unsigned int
599eabdb DB	252	tree_linear_transform (void)
599eabdb DB	253	{
d51157de	254	if (number_of_loops () <= 1)
c2924966	255	return 0;
599eabdb	256
d73be268	257	linear_transform_loops ();
c2924966	258	return 0;
599eabdb DB	259	}
	260
	261	static bool
	262	gate_tree_linear_transform (void)
	263	{
	264	return flag_tree_loop_linear != 0;
	265	}
	266
8ddbbcae	267	struct gimple_opt_pass pass_linear_transform =
599eabdb	268	{
8ddbbcae JH	269	{
8ddbbcae JH	270	GIMPLE_PASS,
599eabdb DB	271	"ltrans", /* name */
	272	gate_tree_linear_transform, /* gate */
	273	tree_linear_transform, /* execute */
	274	NULL, /* sub */
	275	NULL, /* next */
	276	0, /* static_pass_number */
	277	TV_TREE_LINEAR_TRANSFORM, /* tv_id */
	278	PROP_cfg \| PROP_ssa, /* properties_required */
	279	0, /* properties_provided */
	280	0, /* properties_destroyed */
	281	0, /* todo_flags_start */
98b6e9dd	282	TODO_dump_func
1785c05d	283	\| TODO_update_ssa_only_virtuals
8ddbbcae JH	284	\| TODO_ggc_collect /* todo_flags_finish */
8ddbbcae JH	285	}
599eabdb DB	286	};
599eabdb DB	287
f8bf9252 SP	288	/* GRAPHITE optimizations. */
	289
	290	static unsigned int
	291	graphite_transforms (void)
	292	{
	293	if (!current_loops)
	294	return 0;
	295
	296	graphite_transform_loops ();
	297
	298	return 0;
	299	}
	300
	301	static bool
	302	gate_graphite_transforms (void)
	303	{
b8698a0f	304	/* Enable -fgraphite pass if any one of the graphite optimization flags
f8bf9252	305	is turned on. */
98af4c9f SP	306	if (flag_loop_block
	307	\|\| flag_loop_interchange
	308	\|\| flag_loop_strip_mine
	309	\|\| flag_graphite_identity
	310	\|\| flag_loop_parallelize_all
	311	\|\| flag_loop_flatten)
f8bf9252 SP	312	flag_graphite = 1;
	313
	314	return flag_graphite != 0;
	315	}
	316
d4332d00 SP	317	struct gimple_opt_pass pass_graphite =
	318	{
	319	{
	320	GIMPLE_PASS,
	321	"graphite0", /* name */
	322	gate_graphite_transforms, /* gate */
	323	NULL, /* execute */
	324	NULL, /* sub */
	325	NULL, /* next */
	326	0, /* static_pass_number */
	327	TV_GRAPHITE, /* tv_id */
	328	PROP_cfg \| PROP_ssa, /* properties_required */
	329	0, /* properties_provided */
	330	0, /* properties_destroyed */
	331	0, /* todo_flags_start */
	332	0 /* todo_flags_finish */
	333	}
	334	};
	335
f8bf9252 SP	336	struct gimple_opt_pass pass_graphite_transforms =
	337	{
	338	{
	339	GIMPLE_PASS,
	340	"graphite", /* name */
	341	gate_graphite_transforms, /* gate */
	342	graphite_transforms, /* execute */
	343	NULL, /* sub */
	344	NULL, /* next */
	345	0, /* static_pass_number */
	346	TV_GRAPHITE_TRANSFORMS, /* tv_id */
	347	PROP_cfg \| PROP_ssa, /* properties_required */
	348	0, /* properties_provided */
	349	0, /* properties_destroyed */
	350	0, /* todo_flags_start */
98b6e9dd	351	0 /* todo_flags_finish */
f8bf9252 SP	352	}
	353	};
	354
3d8864c0 SP	355	/* Check the correctness of the data dependence analyzers. */
	356
	357	static unsigned int
	358	check_data_deps (void)
	359	{
d51157de	360	if (number_of_loops () <= 1)
3d8864c0 SP	361	return 0;
	362
	363	tree_check_data_deps ();
	364	return 0;
	365	}
	366
	367	static bool
	368	gate_check_data_deps (void)
	369	{
	370	return flag_check_data_deps != 0;
	371	}
	372
8ddbbcae	373	struct gimple_opt_pass pass_check_data_deps =
3d8864c0	374	{
8ddbbcae JH	375	{
8ddbbcae JH	376	GIMPLE_PASS,
3d8864c0 SP	377	"ckdd", /* name */
	378	gate_check_data_deps, /* gate */
	379	check_data_deps, /* execute */
	380	NULL, /* sub */
	381	NULL, /* next */
	382	0, /* static_pass_number */
	383	TV_CHECK_DATA_DEPS, /* tv_id */
	384	PROP_cfg \| PROP_ssa, /* properties_required */
	385	0, /* properties_provided */
	386	0, /* properties_destroyed */
	387	0, /* todo_flags_start */
8ddbbcae JH	388	TODO_dump_func /* todo_flags_finish */
8ddbbcae JH	389	}
3d8864c0 SP	390	};
3d8864c0 SP	391
82b85a85 ZD	392	/* Canonical induction variable creation pass. */
82b85a85 ZD	393
c2924966	394	static unsigned int
82b85a85 ZD	395	tree_ssa_loop_ivcanon (void)
82b85a85 ZD	396	{
d51157de	397	if (number_of_loops () <= 1)
c2924966	398	return 0;
82b85a85	399
d73be268	400	return canonicalize_induction_variables ();
82b85a85 ZD	401	}
	402
	403	static bool
	404	gate_tree_ssa_loop_ivcanon (void)
	405	{
1b08d87d	406	return flag_tree_loop_ivcanon != 0;
82b85a85 ZD	407	}
82b85a85 ZD	408
8ddbbcae	409	struct gimple_opt_pass pass_iv_canon =
82b85a85	410	{
8ddbbcae JH	411	{
8ddbbcae JH	412	GIMPLE_PASS,
82b85a85 ZD	413	"ivcanon", /* name */
	414	gate_tree_ssa_loop_ivcanon, /* gate */
	415	tree_ssa_loop_ivcanon, /* execute */
	416	NULL, /* sub */
	417	NULL, /* next */
	418	0, /* static_pass_number */
	419	TV_TREE_LOOP_IVCANON, /* tv_id */
	420	PROP_cfg \| PROP_ssa, /* properties_required */
	421	0, /* properties_provided */
	422	0, /* properties_destroyed */
	423	0, /* todo_flags_start */
98b6e9dd	424	TODO_dump_func /* todo_flags_finish */
8ddbbcae	425	}
684aaf29 ZD	426	};
	427
	428	/* Propagation of constants using scev. */
	429
	430	static bool
	431	gate_scev_const_prop (void)
	432	{
fbf798fc	433	return flag_tree_scev_cprop;
684aaf29 ZD	434	}
684aaf29 ZD	435
8ddbbcae	436	struct gimple_opt_pass pass_scev_cprop =
684aaf29	437	{
8ddbbcae JH	438	{
8ddbbcae JH	439	GIMPLE_PASS,
684aaf29 ZD	440	"sccp", /* name */
	441	gate_scev_const_prop, /* gate */
	442	scev_const_prop, /* execute */
	443	NULL, /* sub */
	444	NULL, /* next */
	445	0, /* static_pass_number */
	446	TV_SCEV_CONST, /* tv_id */
	447	PROP_cfg \| PROP_ssa, /* properties_required */
	448	0, /* properties_provided */
	449	0, /* properties_destroyed */
	450	0, /* todo_flags_start */
43ec2467	451	TODO_dump_func \| TODO_cleanup_cfg
8ddbbcae	452	\| TODO_update_ssa_only_virtuals
d49195a3	453	/* todo_flags_finish */
8ddbbcae	454	}
b7eae7b8 ZD	455	};
b7eae7b8 ZD	456
f3cd574f ZD	457	/* Record bounds on numbers of iterations of loops. */
f3cd574f ZD	458
c2924966	459	static unsigned int
f3cd574f ZD	460	tree_ssa_loop_bounds (void)
f3cd574f ZD	461	{
d51157de	462	if (number_of_loops () <= 1)
c2924966	463	return 0;
f3cd574f	464
e3488283	465	estimate_numbers_of_iterations (true);
f3cd574f	466	scev_reset ();
c2924966	467	return 0;
f3cd574f ZD	468	}
f3cd574f ZD	469
8ddbbcae	470	struct gimple_opt_pass pass_record_bounds =
f3cd574f	471	{
8ddbbcae JH	472	{
8ddbbcae JH	473	GIMPLE_PASS,
e0a42b0f	474	"record_bounds", / name */
f3cd574f ZD	475	NULL, /* gate */
	476	tree_ssa_loop_bounds, /* execute */
	477	NULL, /* sub */
	478	NULL, /* next */
	479	0, /* static_pass_number */
ccbdbf0a	480	TV_TREE_LOOP_BOUNDS, /* tv_id */
f3cd574f ZD	481	PROP_cfg \| PROP_ssa, /* properties_required */
	482	0, /* properties_provided */
	483	0, /* properties_destroyed */
	484	0, /* todo_flags_start */
8ddbbcae JH	485	0 /* todo_flags_finish */
8ddbbcae JH	486	}
f3cd574f ZD	487	};
f3cd574f ZD	488
82b85a85 ZD	489	/* Complete unrolling of loops. */
82b85a85 ZD	490
c2924966	491	static unsigned int
82b85a85 ZD	492	tree_complete_unroll (void)
82b85a85 ZD	493	{
d51157de	494	if (number_of_loops () <= 1)
c2924966	495	return 0;
82b85a85	496
d73be268 ZD	497	return tree_unroll_loops_completely (flag_unroll_loops
d73be268 ZD	498	\|\| flag_peel_loops
d6e840ee	499	\|\| optimize >= 3, true);
82b85a85 ZD	500	}
	501
	502	static bool
	503	gate_tree_complete_unroll (void)
	504	{
91a01f21	505	return true;
82b85a85 ZD	506	}
82b85a85 ZD	507
8ddbbcae	508	struct gimple_opt_pass pass_complete_unroll =
82b85a85	509	{
8ddbbcae JH	510	{
8ddbbcae JH	511	GIMPLE_PASS,
82b85a85 ZD	512	"cunroll", /* name */
	513	gate_tree_complete_unroll, /* gate */
	514	tree_complete_unroll, /* execute */
	515	NULL, /* sub */
	516	NULL, /* next */
	517	0, /* static_pass_number */
	518	TV_COMPLETE_UNROLL, /* tv_id */
	519	PROP_cfg \| PROP_ssa, /* properties_required */
8b11a64c ZD	520	0, /* properties_provided */
	521	0, /* properties_destroyed */
	522	0, /* todo_flags_start */
98b6e9dd	523	TODO_dump_func
8ddbbcae JH	524	\| TODO_ggc_collect /* todo_flags_finish */
8ddbbcae JH	525	}
8b11a64c ZD	526	};
8b11a64c ZD	527
d6e840ee RG	528	/* Complete unrolling of inner loops. */
	529
	530	static unsigned int
	531	tree_complete_unroll_inner (void)
	532	{
	533	unsigned ret = 0;
	534
	535	loop_optimizer_init (LOOPS_NORMAL
	536	\| LOOPS_HAVE_RECORDED_EXITS);
	537	if (number_of_loops () > 1)
	538	{
	539	scev_initialize ();
	540	ret = tree_unroll_loops_completely (optimize >= 3, false);
	541	free_numbers_of_iterations_estimates ();
	542	scev_finalize ();
	543	}
	544	loop_optimizer_finalize ();
	545
	546	return ret;
	547	}
	548
	549	static bool
	550	gate_tree_complete_unroll_inner (void)
	551	{
	552	return optimize >= 2;
	553	}
	554
	555	struct gimple_opt_pass pass_complete_unrolli =
	556	{
	557	{
	558	GIMPLE_PASS,
	559	"cunrolli", /* name */
	560	gate_tree_complete_unroll_inner, /* gate */
	561	tree_complete_unroll_inner, /* execute */
	562	NULL, /* sub */
	563	NULL, /* next */
	564	0, /* static_pass_number */
	565	TV_COMPLETE_UNROLL, /* tv_id */
	566	PROP_cfg \| PROP_ssa, /* properties_required */
	567	0, /* properties_provided */
	568	0, /* properties_destroyed */
	569	0, /* todo_flags_start */
98b6e9dd	570	TODO_dump_func
d6e840ee RG	571	\| TODO_ggc_collect /* todo_flags_finish */
	572	}
	573	};
	574
5f40b3cb ZD	575	/* Parallelization. */
	576
	577	static bool
	578	gate_tree_parallelize_loops (void)
	579	{
4e9012fd	580	return flag_tree_parallelize_loops > 1;
5f40b3cb ZD	581	}
	582
	583	static unsigned
	584	tree_parallelize_loops (void)
	585	{
	586	if (number_of_loops () <= 1)
	587	return 0;
	588
	589	if (parallelize_loops ())
	590	return TODO_cleanup_cfg \| TODO_rebuild_alias;
	591	return 0;
	592	}
	593
8ddbbcae	594	struct gimple_opt_pass pass_parallelize_loops =
5f40b3cb	595	{
8ddbbcae JH	596	{
8ddbbcae JH	597	GIMPLE_PASS,
5f40b3cb ZD	598	"parloops", /* name */
	599	gate_tree_parallelize_loops, /* gate */
	600	tree_parallelize_loops, /* execute */
	601	NULL, /* sub */
	602	NULL, /* next */
	603	0, /* static_pass_number */
	604	TV_TREE_PARALLELIZE_LOOPS, /* tv_id */
	605	PROP_cfg \| PROP_ssa, /* properties_required */
	606	0, /* properties_provided */
	607	0, /* properties_destroyed */
	608	0, /* todo_flags_start */
98b6e9dd	609	TODO_dump_func /* todo_flags_finish */
8ddbbcae	610	}
5f40b3cb ZD	611	};
5f40b3cb ZD	612
17684618 ZD	613	/* Prefetching. */
17684618 ZD	614
c2924966	615	static unsigned int
17684618 ZD	616	tree_ssa_loop_prefetch (void)
17684618 ZD	617	{
d51157de	618	if (number_of_loops () <= 1)
c2924966	619	return 0;
17684618	620
d73be268	621	return tree_ssa_prefetch_arrays ();
17684618 ZD	622	}
	623
	624	static bool
	625	gate_tree_ssa_loop_prefetch (void)
	626	{
1fbb509a	627	return flag_prefetch_loop_arrays > 0;
17684618 ZD	628	}
17684618 ZD	629
8ddbbcae	630	struct gimple_opt_pass pass_loop_prefetch =
17684618	631	{
8ddbbcae JH	632	{
8ddbbcae JH	633	GIMPLE_PASS,
e324a72f	634	"aprefetch", /* name */
17684618 ZD	635	gate_tree_ssa_loop_prefetch, /* gate */
	636	tree_ssa_loop_prefetch, /* execute */
	637	NULL, /* sub */
	638	NULL, /* next */
	639	0, /* static_pass_number */
	640	TV_TREE_PREFETCH, /* tv_id */
	641	PROP_cfg \| PROP_ssa, /* properties_required */
	642	0, /* properties_provided */
	643	0, /* properties_destroyed */
	644	0, /* todo_flags_start */
98b6e9dd	645	TODO_dump_func /* todo_flags_finish */
8ddbbcae	646	}
17684618 ZD	647	};
17684618 ZD	648
8b11a64c ZD	649	/* Induction variable optimizations. */
8b11a64c ZD	650
c2924966	651	static unsigned int
8b11a64c ZD	652	tree_ssa_loop_ivopts (void)
8b11a64c ZD	653	{
d51157de	654	if (number_of_loops () <= 1)
c2924966	655	return 0;
8b11a64c	656
d73be268	657	tree_ssa_iv_optimize ();
c2924966	658	return 0;
8b11a64c ZD	659	}
	660
	661	static bool
	662	gate_tree_ssa_loop_ivopts (void)
	663	{
	664	return flag_ivopts != 0;
	665	}
	666
8ddbbcae	667	struct gimple_opt_pass pass_iv_optimize =
8b11a64c	668	{
8ddbbcae JH	669	{
8ddbbcae JH	670	GIMPLE_PASS,
8b11a64c ZD	671	"ivopts", /* name */
	672	gate_tree_ssa_loop_ivopts, /* gate */
	673	tree_ssa_loop_ivopts, /* execute */
	674	NULL, /* sub */
	675	NULL, /* next */
	676	0, /* static_pass_number */
	677	TV_TREE_LOOP_IVOPTS, /* tv_id */
	678	PROP_cfg \| PROP_ssa, /* properties_required */
82b85a85 ZD	679	0, /* properties_provided */
	680	0, /* properties_destroyed */
	681	0, /* todo_flags_start */
98b6e9dd	682	TODO_dump_func \| TODO_update_ssa \| TODO_ggc_collect /* todo_flags_finish */
8ddbbcae	683	}
82b85a85 ZD	684	};
82b85a85 ZD	685
c66b6c66 ZD	686	/* Loop optimizer finalization. */
c66b6c66 ZD	687
c2924966	688	static unsigned int
c66b6c66 ZD	689	tree_ssa_loop_done (void)
c66b6c66 ZD	690	{
d73be268	691	free_numbers_of_iterations_estimates ();
82b85a85	692	scev_finalize ();
598ec7bd	693	loop_optimizer_finalize ();
c2924966	694	return 0;
c66b6c66	695	}
b8698a0f L	696
b8698a0f L	697	struct gimple_opt_pass pass_tree_loop_done =
c66b6c66	698	{
8ddbbcae JH	699	{
8ddbbcae JH	700	GIMPLE_PASS,
c66b6c66 ZD	701	"loopdone", /* name */
	702	NULL, /* gate */
	703	tree_ssa_loop_done, /* execute */
	704	NULL, /* sub */
	705	NULL, /* next */
	706	0, /* static_pass_number */
87c11134	707	TV_TREE_LOOP_FINI, /* tv_id */
c66b6c66 ZD	708	PROP_cfg, /* properties_required */
	709	0, /* properties_provided */
	710	0, /* properties_destroyed */
	711	0, /* todo_flags_start */
8ddbbcae JH	712	TODO_cleanup_cfg \| TODO_dump_func /* todo_flags_finish */
8ddbbcae JH	713	}
c66b6c66	714	};