1 /* Loop optimizations over tree-ssa.
2 Copyright (C) 2003-2014 Free Software Foundation, Inc.
4 This file is part of GCC.
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
8 Free Software Foundation; either version 3, or (at your option) any
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
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
26 #include "basic-block.h"
27 #include "tree-ssa-alias.h"
28 #include "internal-fn.h"
29 #include "gimple-expr.h"
32 #include "gimple-iterator.h"
33 #include "tree-ssa-loop-ivopts.h"
34 #include "tree-ssa-loop-manip.h"
35 #include "tree-ssa-loop-niter.h"
36 #include "tree-ssa-loop.h"
37 #include "tree-pass.h"
40 #include "tree-inline.h"
41 #include "tree-scalar-evolution.h"
42 #include "diagnostic-core.h"
43 #include "tree-vectorizer.h"
46 /* Gate for loop pass group. The group is controlled by -ftree-loop-optimize
47 but we also avoid running it when the IL doesn't contain any loop. */
50 gate_loop (function
*fn
)
52 if (!flag_tree_loop_optimize
)
55 /* For -fdump-passes which runs before loop discovery print the
56 state of -ftree-loop-optimize. */
57 if (!loops_for_fn (fn
))
60 /* Make sure to drop / re-discover loops when necessary. */
61 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
62 fix_loop_structure (NULL
);
63 return number_of_loops (fn
) > 1;
66 /* The loop superpass. */
70 const pass_data pass_data_tree_loop
=
72 GIMPLE_PASS
, /* type */
74 OPTGROUP_LOOP
, /* optinfo_flags */
75 TV_TREE_LOOP
, /* tv_id */
76 PROP_cfg
, /* properties_required */
77 0, /* properties_provided */
78 0, /* properties_destroyed */
79 0, /* todo_flags_start */
80 0, /* todo_flags_finish */
83 class pass_tree_loop
: public gimple_opt_pass
86 pass_tree_loop (gcc::context
*ctxt
)
87 : gimple_opt_pass (pass_data_tree_loop
, ctxt
)
90 /* opt_pass methods: */
91 virtual bool gate (function
*fn
) { return gate_loop (fn
); }
93 }; // class pass_tree_loop
98 make_pass_tree_loop (gcc::context
*ctxt
)
100 return new pass_tree_loop (ctxt
);
103 /* The no-loop superpass. */
107 const pass_data pass_data_tree_no_loop
=
109 GIMPLE_PASS
, /* type */
110 "no_loop", /* name */
111 OPTGROUP_NONE
, /* optinfo_flags */
112 TV_TREE_NOLOOP
, /* tv_id */
113 PROP_cfg
, /* properties_required */
114 0, /* properties_provided */
115 0, /* properties_destroyed */
116 0, /* todo_flags_start */
117 0, /* todo_flags_finish */
120 class pass_tree_no_loop
: public gimple_opt_pass
123 pass_tree_no_loop (gcc::context
*ctxt
)
124 : gimple_opt_pass (pass_data_tree_no_loop
, ctxt
)
127 /* opt_pass methods: */
128 virtual bool gate (function
*fn
) { return !gate_loop (fn
); }
130 }; // class pass_tree_no_loop
135 make_pass_tree_no_loop (gcc::context
*ctxt
)
137 return new pass_tree_no_loop (ctxt
);
141 /* Loop optimizer initialization. */
145 const pass_data pass_data_tree_loop_init
=
147 GIMPLE_PASS
, /* type */
148 "loopinit", /* name */
149 OPTGROUP_LOOP
, /* optinfo_flags */
151 PROP_cfg
, /* properties_required */
152 0, /* properties_provided */
153 0, /* properties_destroyed */
154 0, /* todo_flags_start */
155 0, /* todo_flags_finish */
158 class pass_tree_loop_init
: public gimple_opt_pass
161 pass_tree_loop_init (gcc::context
*ctxt
)
162 : gimple_opt_pass (pass_data_tree_loop_init
, ctxt
)
165 /* opt_pass methods: */
166 virtual unsigned int execute (function
*);
168 }; // class pass_tree_loop_init
171 pass_tree_loop_init::execute (function
*fun
)
173 loop_optimizer_init (LOOPS_NORMAL
174 | LOOPS_HAVE_RECORDED_EXITS
);
175 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
177 /* We might discover new loops, e.g. when turning irreducible
178 regions into reducible. */
181 if (number_of_loops (fun
) <= 1)
190 make_pass_tree_loop_init (gcc::context
*ctxt
)
192 return new pass_tree_loop_init (ctxt
);
195 /* Loop autovectorization. */
199 const pass_data pass_data_vectorize
=
201 GIMPLE_PASS
, /* type */
203 OPTGROUP_LOOP
| OPTGROUP_VEC
, /* optinfo_flags */
204 TV_TREE_VECTORIZATION
, /* tv_id */
205 ( PROP_cfg
| PROP_ssa
), /* properties_required */
206 0, /* properties_provided */
207 0, /* properties_destroyed */
208 0, /* todo_flags_start */
209 0, /* todo_flags_finish */
212 class pass_vectorize
: public gimple_opt_pass
215 pass_vectorize (gcc::context
*ctxt
)
216 : gimple_opt_pass (pass_data_vectorize
, ctxt
)
219 /* opt_pass methods: */
220 virtual bool gate (function
*fun
)
222 return flag_tree_loop_vectorize
|| fun
->has_force_vectorize_loops
;
225 virtual unsigned int execute (function
*);
227 }; // class pass_vectorize
230 pass_vectorize::execute (function
*fun
)
232 if (number_of_loops (fun
) <= 1)
235 return vectorize_loops ();
241 make_pass_vectorize (gcc::context
*ctxt
)
243 return new pass_vectorize (ctxt
);
246 /* Check the correctness of the data dependence analyzers. */
250 const pass_data pass_data_check_data_deps
=
252 GIMPLE_PASS
, /* type */
254 OPTGROUP_LOOP
, /* optinfo_flags */
255 TV_CHECK_DATA_DEPS
, /* tv_id */
256 ( PROP_cfg
| PROP_ssa
), /* properties_required */
257 0, /* properties_provided */
258 0, /* properties_destroyed */
259 0, /* todo_flags_start */
260 0, /* todo_flags_finish */
263 class pass_check_data_deps
: public gimple_opt_pass
266 pass_check_data_deps (gcc::context
*ctxt
)
267 : gimple_opt_pass (pass_data_check_data_deps
, ctxt
)
270 /* opt_pass methods: */
271 virtual bool gate (function
*) { return flag_check_data_deps
!= 0; }
272 virtual unsigned int execute (function
*);
274 }; // class pass_check_data_deps
277 pass_check_data_deps::execute (function
*fun
)
279 if (number_of_loops (fun
) <= 1)
282 tree_check_data_deps ();
289 make_pass_check_data_deps (gcc::context
*ctxt
)
291 return new pass_check_data_deps (ctxt
);
294 /* Propagation of constants using scev. */
298 const pass_data pass_data_scev_cprop
=
300 GIMPLE_PASS
, /* type */
302 OPTGROUP_LOOP
, /* optinfo_flags */
303 TV_SCEV_CONST
, /* tv_id */
304 ( PROP_cfg
| PROP_ssa
), /* properties_required */
305 0, /* properties_provided */
306 0, /* properties_destroyed */
307 0, /* todo_flags_start */
309 | TODO_update_ssa_only_virtuals
), /* todo_flags_finish */
312 class pass_scev_cprop
: public gimple_opt_pass
315 pass_scev_cprop (gcc::context
*ctxt
)
316 : gimple_opt_pass (pass_data_scev_cprop
, ctxt
)
319 /* opt_pass methods: */
320 virtual bool gate (function
*) { return flag_tree_scev_cprop
; }
321 virtual unsigned int execute (function
*) { return scev_const_prop (); }
323 }; // class pass_scev_cprop
328 make_pass_scev_cprop (gcc::context
*ctxt
)
330 return new pass_scev_cprop (ctxt
);
333 /* Record bounds on numbers of iterations of loops. */
337 const pass_data pass_data_record_bounds
=
339 GIMPLE_PASS
, /* type */
340 "*record_bounds", /* name */
341 OPTGROUP_NONE
, /* optinfo_flags */
342 TV_TREE_LOOP_BOUNDS
, /* tv_id */
343 ( PROP_cfg
| PROP_ssa
), /* properties_required */
344 0, /* properties_provided */
345 0, /* properties_destroyed */
346 0, /* todo_flags_start */
347 0, /* todo_flags_finish */
350 class pass_record_bounds
: public gimple_opt_pass
353 pass_record_bounds (gcc::context
*ctxt
)
354 : gimple_opt_pass (pass_data_record_bounds
, ctxt
)
357 /* opt_pass methods: */
358 virtual unsigned int execute (function
*);
360 }; // class pass_record_bounds
363 pass_record_bounds::execute (function
*fun
)
365 if (number_of_loops (fun
) <= 1)
368 estimate_numbers_of_iterations ();
376 make_pass_record_bounds (gcc::context
*ctxt
)
378 return new pass_record_bounds (ctxt
);
381 /* Induction variable optimizations. */
385 const pass_data pass_data_iv_optimize
=
387 GIMPLE_PASS
, /* type */
389 OPTGROUP_LOOP
, /* optinfo_flags */
390 TV_TREE_LOOP_IVOPTS
, /* tv_id */
391 ( PROP_cfg
| PROP_ssa
), /* properties_required */
392 0, /* properties_provided */
393 0, /* properties_destroyed */
394 0, /* todo_flags_start */
395 TODO_update_ssa
, /* todo_flags_finish */
398 class pass_iv_optimize
: public gimple_opt_pass
401 pass_iv_optimize (gcc::context
*ctxt
)
402 : gimple_opt_pass (pass_data_iv_optimize
, ctxt
)
405 /* opt_pass methods: */
406 virtual bool gate (function
*) { return flag_ivopts
!= 0; }
407 virtual unsigned int execute (function
*);
409 }; // class pass_iv_optimize
412 pass_iv_optimize::execute (function
*fun
)
414 if (number_of_loops (fun
) <= 1)
417 tree_ssa_iv_optimize ();
424 make_pass_iv_optimize (gcc::context
*ctxt
)
426 return new pass_iv_optimize (ctxt
);
429 /* Loop optimizer finalization. */
432 tree_ssa_loop_done (void)
434 free_numbers_of_iterations_estimates ();
436 loop_optimizer_finalize ();
442 const pass_data pass_data_tree_loop_done
=
444 GIMPLE_PASS
, /* type */
445 "loopdone", /* name */
446 OPTGROUP_LOOP
, /* optinfo_flags */
448 PROP_cfg
, /* properties_required */
449 0, /* properties_provided */
450 0, /* properties_destroyed */
451 0, /* todo_flags_start */
452 TODO_cleanup_cfg
, /* todo_flags_finish */
455 class pass_tree_loop_done
: public gimple_opt_pass
458 pass_tree_loop_done (gcc::context
*ctxt
)
459 : gimple_opt_pass (pass_data_tree_loop_done
, ctxt
)
462 /* opt_pass methods: */
463 virtual unsigned int execute (function
*) { return tree_ssa_loop_done (); }
465 }; // class pass_tree_loop_done
470 make_pass_tree_loop_done (gcc::context
*ctxt
)
472 return new pass_tree_loop_done (ctxt
);
475 /* Calls CBCK for each index in memory reference ADDR_P. There are two
476 kinds situations handled; in each of these cases, the memory reference
477 and DATA are passed to the callback:
479 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
480 pass the pointer to the index to the callback.
482 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
483 pointer to addr to the callback.
485 If the callback returns false, the whole search stops and false is returned.
486 Otherwise the function returns true after traversing through the whole
487 reference *ADDR_P. */
490 for_each_index (tree
*addr_p
, bool (*cbck
) (tree
, tree
*, void *), void *data
)
494 for (; ; addr_p
= nxt
)
496 switch (TREE_CODE (*addr_p
))
499 return cbck (*addr_p
, addr_p
, data
);
502 nxt
= &TREE_OPERAND (*addr_p
, 0);
503 return cbck (*addr_p
, nxt
, data
);
506 case VIEW_CONVERT_EXPR
:
509 nxt
= &TREE_OPERAND (*addr_p
, 0);
513 /* If the component has varying offset, it behaves like index
515 idx
= &TREE_OPERAND (*addr_p
, 2);
517 && !cbck (*addr_p
, idx
, data
))
520 nxt
= &TREE_OPERAND (*addr_p
, 0);
524 case ARRAY_RANGE_REF
:
525 nxt
= &TREE_OPERAND (*addr_p
, 0);
526 if (!cbck (*addr_p
, &TREE_OPERAND (*addr_p
, 1), data
))
544 gcc_assert (is_gimple_min_invariant (*addr_p
));
548 idx
= &TMR_BASE (*addr_p
);
550 && !cbck (*addr_p
, idx
, data
))
552 idx
= &TMR_INDEX (*addr_p
);
554 && !cbck (*addr_p
, idx
, data
))
556 idx
= &TMR_INDEX2 (*addr_p
);
558 && !cbck (*addr_p
, idx
, data
))
569 /* The name and the length of the currently generated variable
571 #define MAX_LSM_NAME_LENGTH 40
572 static char lsm_tmp_name
[MAX_LSM_NAME_LENGTH
+ 1];
573 static int lsm_tmp_name_length
;
575 /* Adds S to lsm_tmp_name. */
578 lsm_tmp_name_add (const char *s
)
580 int l
= strlen (s
) + lsm_tmp_name_length
;
581 if (l
> MAX_LSM_NAME_LENGTH
)
584 strcpy (lsm_tmp_name
+ lsm_tmp_name_length
, s
);
585 lsm_tmp_name_length
= l
;
588 /* Stores the name for temporary variable that replaces REF to
592 gen_lsm_tmp_name (tree ref
)
596 switch (TREE_CODE (ref
))
600 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
601 lsm_tmp_name_add ("_");
605 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
609 case VIEW_CONVERT_EXPR
:
610 case ARRAY_RANGE_REF
:
611 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
615 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
616 lsm_tmp_name_add ("_RE");
620 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
621 lsm_tmp_name_add ("_IM");
625 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
626 lsm_tmp_name_add ("_");
627 name
= get_name (TREE_OPERAND (ref
, 1));
630 lsm_tmp_name_add (name
);
634 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
635 lsm_tmp_name_add ("_I");
641 name
= get_name (ref
);
644 lsm_tmp_name_add (name
);
648 lsm_tmp_name_add ("S");
652 lsm_tmp_name_add ("R");
664 /* Determines name for temporary variable that replaces REF.
665 The name is accumulated into the lsm_tmp_name variable.
666 N is added to the name of the temporary. */
669 get_lsm_tmp_name (tree ref
, unsigned n
, const char *suffix
)
673 lsm_tmp_name_length
= 0;
674 gen_lsm_tmp_name (ref
);
675 lsm_tmp_name_add ("_lsm");
680 lsm_tmp_name_add (ns
);
684 lsm_tmp_name_add (suffix
);
687 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */
690 tree_num_loop_insns (struct loop
*loop
, eni_weights
*weights
)
692 basic_block
*body
= get_loop_body (loop
);
693 gimple_stmt_iterator gsi
;
694 unsigned size
= 0, i
;
696 for (i
= 0; i
< loop
->num_nodes
; i
++)
697 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
698 size
+= estimate_num_insns (gsi_stmt (gsi
), weights
);