1 /* Loop optimizations over tree-ssa.
2 Copyright (C) 2003-2013 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"
28 #include "tree-ssa-loop-ivopts.h"
29 #include "tree-ssa-loop-manip.h"
30 #include "tree-ssa-loop-niter.h"
31 #include "tree-ssa-loop.h"
32 #include "tree-pass.h"
35 #include "tree-inline.h"
36 #include "tree-scalar-evolution.h"
37 #include "diagnostic-core.h"
38 #include "tree-vectorizer.h"
40 /* The loop superpass. */
45 return flag_tree_loop_optimize
!= 0;
50 const pass_data pass_data_tree_loop
=
52 GIMPLE_PASS
, /* type */
54 OPTGROUP_LOOP
, /* optinfo_flags */
56 false, /* has_execute */
57 TV_TREE_LOOP
, /* tv_id */
58 PROP_cfg
, /* properties_required */
59 0, /* properties_provided */
60 0, /* properties_destroyed */
61 0, /* todo_flags_start */
62 TODO_verify_ssa
, /* todo_flags_finish */
65 class pass_tree_loop
: public gimple_opt_pass
68 pass_tree_loop (gcc::context
*ctxt
)
69 : gimple_opt_pass (pass_data_tree_loop
, ctxt
)
72 /* opt_pass methods: */
73 bool gate () { return gate_tree_loop (); }
75 }; // class pass_tree_loop
80 make_pass_tree_loop (gcc::context
*ctxt
)
82 return new pass_tree_loop (ctxt
);
85 /* Loop optimizer initialization. */
88 tree_ssa_loop_init (void)
90 loop_optimizer_init (LOOPS_NORMAL
91 | LOOPS_HAVE_RECORDED_EXITS
);
92 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
94 /* We might discover new loops, e.g. when turning irreducible
95 regions into reducible. */
98 if (number_of_loops (cfun
) <= 1)
106 const pass_data pass_data_tree_loop_init
=
108 GIMPLE_PASS
, /* type */
109 "loopinit", /* name */
110 OPTGROUP_LOOP
, /* optinfo_flags */
111 false, /* has_gate */
112 true, /* has_execute */
114 PROP_cfg
, /* properties_required */
115 0, /* properties_provided */
116 0, /* properties_destroyed */
117 0, /* todo_flags_start */
118 0, /* todo_flags_finish */
121 class pass_tree_loop_init
: public gimple_opt_pass
124 pass_tree_loop_init (gcc::context
*ctxt
)
125 : gimple_opt_pass (pass_data_tree_loop_init
, ctxt
)
128 /* opt_pass methods: */
129 unsigned int execute () { return tree_ssa_loop_init (); }
131 }; // class pass_tree_loop_init
136 make_pass_tree_loop_init (gcc::context
*ctxt
)
138 return new pass_tree_loop_init (ctxt
);
141 /* Loop autovectorization. */
144 tree_loop_vectorize (void)
146 if (number_of_loops (cfun
) <= 1)
149 return vectorize_loops ();
153 gate_tree_loop_vectorize (void)
155 return flag_tree_loop_vectorize
|| cfun
->has_force_vect_loops
;
160 const pass_data pass_data_vectorize
=
162 GIMPLE_PASS
, /* type */
164 OPTGROUP_LOOP
| OPTGROUP_VEC
, /* optinfo_flags */
166 true, /* has_execute */
167 TV_TREE_VECTORIZATION
, /* tv_id */
168 ( PROP_cfg
| PROP_ssa
), /* properties_required */
169 0, /* properties_provided */
170 0, /* properties_destroyed */
171 0, /* todo_flags_start */
172 0, /* todo_flags_finish */
175 class pass_vectorize
: public gimple_opt_pass
178 pass_vectorize (gcc::context
*ctxt
)
179 : gimple_opt_pass (pass_data_vectorize
, ctxt
)
182 /* opt_pass methods: */
183 bool gate () { return gate_tree_loop_vectorize (); }
184 unsigned int execute () { return tree_loop_vectorize (); }
186 }; // class pass_vectorize
191 make_pass_vectorize (gcc::context
*ctxt
)
193 return new pass_vectorize (ctxt
);
196 /* Check the correctness of the data dependence analyzers. */
199 check_data_deps (void)
201 if (number_of_loops (cfun
) <= 1)
204 tree_check_data_deps ();
209 gate_check_data_deps (void)
211 return flag_check_data_deps
!= 0;
216 const pass_data pass_data_check_data_deps
=
218 GIMPLE_PASS
, /* type */
220 OPTGROUP_LOOP
, /* optinfo_flags */
222 true, /* has_execute */
223 TV_CHECK_DATA_DEPS
, /* tv_id */
224 ( PROP_cfg
| PROP_ssa
), /* properties_required */
225 0, /* properties_provided */
226 0, /* properties_destroyed */
227 0, /* todo_flags_start */
228 0, /* todo_flags_finish */
231 class pass_check_data_deps
: public gimple_opt_pass
234 pass_check_data_deps (gcc::context
*ctxt
)
235 : gimple_opt_pass (pass_data_check_data_deps
, ctxt
)
238 /* opt_pass methods: */
239 bool gate () { return gate_check_data_deps (); }
240 unsigned int execute () { return check_data_deps (); }
242 }; // class pass_check_data_deps
247 make_pass_check_data_deps (gcc::context
*ctxt
)
249 return new pass_check_data_deps (ctxt
);
252 /* Propagation of constants using scev. */
255 gate_scev_const_prop (void)
257 return flag_tree_scev_cprop
;
262 const pass_data pass_data_scev_cprop
=
264 GIMPLE_PASS
, /* type */
266 OPTGROUP_LOOP
, /* optinfo_flags */
268 true, /* has_execute */
269 TV_SCEV_CONST
, /* tv_id */
270 ( PROP_cfg
| PROP_ssa
), /* properties_required */
271 0, /* properties_provided */
272 0, /* properties_destroyed */
273 0, /* todo_flags_start */
275 | TODO_update_ssa_only_virtuals
), /* todo_flags_finish */
278 class pass_scev_cprop
: public gimple_opt_pass
281 pass_scev_cprop (gcc::context
*ctxt
)
282 : gimple_opt_pass (pass_data_scev_cprop
, ctxt
)
285 /* opt_pass methods: */
286 bool gate () { return gate_scev_const_prop (); }
287 unsigned int execute () { return scev_const_prop (); }
289 }; // class pass_scev_cprop
294 make_pass_scev_cprop (gcc::context
*ctxt
)
296 return new pass_scev_cprop (ctxt
);
299 /* Record bounds on numbers of iterations of loops. */
302 tree_ssa_loop_bounds (void)
304 if (number_of_loops (cfun
) <= 1)
307 estimate_numbers_of_iterations ();
314 const pass_data pass_data_record_bounds
=
316 GIMPLE_PASS
, /* type */
317 "*record_bounds", /* name */
318 OPTGROUP_NONE
, /* optinfo_flags */
319 false, /* has_gate */
320 true, /* has_execute */
321 TV_TREE_LOOP_BOUNDS
, /* tv_id */
322 ( PROP_cfg
| PROP_ssa
), /* properties_required */
323 0, /* properties_provided */
324 0, /* properties_destroyed */
325 0, /* todo_flags_start */
326 0, /* todo_flags_finish */
329 class pass_record_bounds
: public gimple_opt_pass
332 pass_record_bounds (gcc::context
*ctxt
)
333 : gimple_opt_pass (pass_data_record_bounds
, ctxt
)
336 /* opt_pass methods: */
337 unsigned int execute () { return tree_ssa_loop_bounds (); }
339 }; // class pass_record_bounds
344 make_pass_record_bounds (gcc::context
*ctxt
)
346 return new pass_record_bounds (ctxt
);
349 /* Induction variable optimizations. */
352 tree_ssa_loop_ivopts (void)
354 if (number_of_loops (cfun
) <= 1)
357 tree_ssa_iv_optimize ();
362 gate_tree_ssa_loop_ivopts (void)
364 return flag_ivopts
!= 0;
369 const pass_data pass_data_iv_optimize
=
371 GIMPLE_PASS
, /* type */
373 OPTGROUP_LOOP
, /* optinfo_flags */
375 true, /* has_execute */
376 TV_TREE_LOOP_IVOPTS
, /* tv_id */
377 ( PROP_cfg
| PROP_ssa
), /* properties_required */
378 0, /* properties_provided */
379 0, /* properties_destroyed */
380 0, /* todo_flags_start */
381 TODO_update_ssa
, /* todo_flags_finish */
384 class pass_iv_optimize
: public gimple_opt_pass
387 pass_iv_optimize (gcc::context
*ctxt
)
388 : gimple_opt_pass (pass_data_iv_optimize
, ctxt
)
391 /* opt_pass methods: */
392 bool gate () { return gate_tree_ssa_loop_ivopts (); }
393 unsigned int execute () { return tree_ssa_loop_ivopts (); }
395 }; // class pass_iv_optimize
400 make_pass_iv_optimize (gcc::context
*ctxt
)
402 return new pass_iv_optimize (ctxt
);
405 /* Loop optimizer finalization. */
408 tree_ssa_loop_done (void)
410 free_numbers_of_iterations_estimates ();
412 loop_optimizer_finalize ();
418 const pass_data pass_data_tree_loop_done
=
420 GIMPLE_PASS
, /* type */
421 "loopdone", /* name */
422 OPTGROUP_LOOP
, /* optinfo_flags */
423 false, /* has_gate */
424 true, /* has_execute */
426 PROP_cfg
, /* properties_required */
427 0, /* properties_provided */
428 0, /* properties_destroyed */
429 0, /* todo_flags_start */
430 ( TODO_cleanup_cfg
| TODO_verify_flow
), /* todo_flags_finish */
433 class pass_tree_loop_done
: public gimple_opt_pass
436 pass_tree_loop_done (gcc::context
*ctxt
)
437 : gimple_opt_pass (pass_data_tree_loop_done
, ctxt
)
440 /* opt_pass methods: */
441 unsigned int execute () { return tree_ssa_loop_done (); }
443 }; // class pass_tree_loop_done
448 make_pass_tree_loop_done (gcc::context
*ctxt
)
450 return new pass_tree_loop_done (ctxt
);
453 /* Calls CBCK for each index in memory reference ADDR_P. There are two
454 kinds situations handled; in each of these cases, the memory reference
455 and DATA are passed to the callback:
457 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
458 pass the pointer to the index to the callback.
460 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
461 pointer to addr to the callback.
463 If the callback returns false, the whole search stops and false is returned.
464 Otherwise the function returns true after traversing through the whole
465 reference *ADDR_P. */
468 for_each_index (tree
*addr_p
, bool (*cbck
) (tree
, tree
*, void *), void *data
)
472 for (; ; addr_p
= nxt
)
474 switch (TREE_CODE (*addr_p
))
477 return cbck (*addr_p
, addr_p
, data
);
480 nxt
= &TREE_OPERAND (*addr_p
, 0);
481 return cbck (*addr_p
, nxt
, data
);
484 case VIEW_CONVERT_EXPR
:
487 nxt
= &TREE_OPERAND (*addr_p
, 0);
491 /* If the component has varying offset, it behaves like index
493 idx
= &TREE_OPERAND (*addr_p
, 2);
495 && !cbck (*addr_p
, idx
, data
))
498 nxt
= &TREE_OPERAND (*addr_p
, 0);
502 case ARRAY_RANGE_REF
:
503 nxt
= &TREE_OPERAND (*addr_p
, 0);
504 if (!cbck (*addr_p
, &TREE_OPERAND (*addr_p
, 1), data
))
522 gcc_assert (is_gimple_min_invariant (*addr_p
));
526 idx
= &TMR_BASE (*addr_p
);
528 && !cbck (*addr_p
, idx
, data
))
530 idx
= &TMR_INDEX (*addr_p
);
532 && !cbck (*addr_p
, idx
, data
))
534 idx
= &TMR_INDEX2 (*addr_p
);
536 && !cbck (*addr_p
, idx
, data
))
547 /* The name and the length of the currently generated variable
549 #define MAX_LSM_NAME_LENGTH 40
550 static char lsm_tmp_name
[MAX_LSM_NAME_LENGTH
+ 1];
551 static int lsm_tmp_name_length
;
553 /* Adds S to lsm_tmp_name. */
556 lsm_tmp_name_add (const char *s
)
558 int l
= strlen (s
) + lsm_tmp_name_length
;
559 if (l
> MAX_LSM_NAME_LENGTH
)
562 strcpy (lsm_tmp_name
+ lsm_tmp_name_length
, s
);
563 lsm_tmp_name_length
= l
;
566 /* Stores the name for temporary variable that replaces REF to
570 gen_lsm_tmp_name (tree ref
)
574 switch (TREE_CODE (ref
))
578 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
579 lsm_tmp_name_add ("_");
583 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
587 case VIEW_CONVERT_EXPR
:
588 case ARRAY_RANGE_REF
:
589 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
593 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
594 lsm_tmp_name_add ("_RE");
598 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
599 lsm_tmp_name_add ("_IM");
603 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
604 lsm_tmp_name_add ("_");
605 name
= get_name (TREE_OPERAND (ref
, 1));
608 lsm_tmp_name_add (name
);
612 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
613 lsm_tmp_name_add ("_I");
619 name
= get_name (ref
);
622 lsm_tmp_name_add (name
);
626 lsm_tmp_name_add ("S");
630 lsm_tmp_name_add ("R");
642 /* Determines name for temporary variable that replaces REF.
643 The name is accumulated into the lsm_tmp_name variable.
644 N is added to the name of the temporary. */
647 get_lsm_tmp_name (tree ref
, unsigned n
, const char *suffix
)
651 lsm_tmp_name_length
= 0;
652 gen_lsm_tmp_name (ref
);
653 lsm_tmp_name_add ("_lsm");
658 lsm_tmp_name_add (ns
);
662 lsm_tmp_name_add (suffix
);
665 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */
668 tree_num_loop_insns (struct loop
*loop
, eni_weights
*weights
)
670 basic_block
*body
= get_loop_body (loop
);
671 gimple_stmt_iterator gsi
;
672 unsigned size
= 0, i
;
674 for (i
= 0; i
< loop
->num_nodes
; i
++)
675 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
676 size
+= estimate_num_insns (gsi_stmt (gsi
), weights
);