1 /* Loop optimizations over tree-ssa.
2 Copyright (C) 2003-2022 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 "tree-pass.h"
29 #include "fold-const.h"
30 #include "gimple-iterator.h"
31 #include "tree-ssa-loop-ivopts.h"
32 #include "tree-ssa-loop-manip.h"
33 #include "tree-ssa-loop-niter.h"
34 #include "tree-ssa-loop.h"
36 #include "tree-inline.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-vectorizer.h"
39 #include "omp-general.h"
40 #include "diagnostic-core.h"
41 #include "stringpool.h"
45 /* A pass making sure loops are fixed up. */
49 const pass_data pass_data_fix_loops
=
51 GIMPLE_PASS
, /* type */
52 "fix_loops", /* name */
53 OPTGROUP_LOOP
, /* optinfo_flags */
54 TV_TREE_LOOP
, /* tv_id */
55 PROP_cfg
, /* properties_required */
56 0, /* properties_provided */
57 0, /* properties_destroyed */
58 0, /* todo_flags_start */
59 0, /* todo_flags_finish */
62 class pass_fix_loops
: public gimple_opt_pass
65 pass_fix_loops (gcc::context
*ctxt
)
66 : gimple_opt_pass (pass_data_fix_loops
, ctxt
)
69 /* opt_pass methods: */
70 virtual bool gate (function
*) { return flag_tree_loop_optimize
; }
72 virtual unsigned int execute (function
*fn
);
73 }; // class pass_fix_loops
76 pass_fix_loops::execute (function
*)
78 if (loops_state_satisfies_p (LOOPS_NEED_FIXUP
))
80 calculate_dominance_info (CDI_DOMINATORS
);
81 fix_loop_structure (NULL
);
89 make_pass_fix_loops (gcc::context
*ctxt
)
91 return new pass_fix_loops (ctxt
);
95 /* Gate for loop pass group. The group is controlled by -ftree-loop-optimize
96 but we also avoid running it when the IL doesn't contain any loop. */
99 gate_loop (function
*fn
)
101 if (!flag_tree_loop_optimize
)
104 /* For -fdump-passes which runs before loop discovery print the
105 state of -ftree-loop-optimize. */
106 if (!loops_for_fn (fn
))
109 return number_of_loops (fn
) > 1;
112 /* The loop superpass. */
116 const pass_data pass_data_tree_loop
=
118 GIMPLE_PASS
, /* type */
120 OPTGROUP_LOOP
, /* optinfo_flags */
121 TV_TREE_LOOP
, /* tv_id */
122 PROP_cfg
, /* properties_required */
123 0, /* properties_provided */
124 0, /* properties_destroyed */
125 0, /* todo_flags_start */
126 0, /* todo_flags_finish */
129 class pass_tree_loop
: public gimple_opt_pass
132 pass_tree_loop (gcc::context
*ctxt
)
133 : gimple_opt_pass (pass_data_tree_loop
, ctxt
)
136 /* opt_pass methods: */
137 virtual bool gate (function
*fn
) { return gate_loop (fn
); }
139 }; // class pass_tree_loop
144 make_pass_tree_loop (gcc::context
*ctxt
)
146 return new pass_tree_loop (ctxt
);
149 /* Gate for oacc kernels pass group. */
152 gate_oacc_kernels (function
*fn
)
157 if (!lookup_attribute ("oacc kernels", DECL_ATTRIBUTES (fn
->decl
)))
160 for (auto loop
: loops_list (cfun
, 0))
161 if (loop
->in_oacc_kernels_region
)
167 /* The oacc kernels superpass. */
171 const pass_data pass_data_oacc_kernels
=
173 GIMPLE_PASS
, /* type */
174 "oacc_kernels", /* name */
175 OPTGROUP_LOOP
, /* optinfo_flags */
176 TV_TREE_LOOP
, /* tv_id */
177 PROP_cfg
, /* properties_required */
178 0, /* properties_provided */
179 0, /* properties_destroyed */
180 0, /* todo_flags_start */
181 0, /* todo_flags_finish */
184 class pass_oacc_kernels
: public gimple_opt_pass
187 pass_oacc_kernels (gcc::context
*ctxt
)
188 : gimple_opt_pass (pass_data_oacc_kernels
, ctxt
)
191 /* opt_pass methods: */
192 virtual bool gate (function
*fn
) { return gate_oacc_kernels (fn
); }
194 }; // class pass_oacc_kernels
199 make_pass_oacc_kernels (gcc::context
*ctxt
)
201 return new pass_oacc_kernels (ctxt
);
204 /* The ipa oacc superpass. */
208 const pass_data pass_data_ipa_oacc
=
210 SIMPLE_IPA_PASS
, /* type */
211 "ipa_oacc", /* name */
212 OPTGROUP_LOOP
, /* optinfo_flags */
213 TV_TREE_LOOP
, /* tv_id */
214 PROP_cfg
, /* properties_required */
215 0, /* properties_provided */
216 0, /* properties_destroyed */
217 0, /* todo_flags_start */
218 0, /* todo_flags_finish */
221 class pass_ipa_oacc
: public simple_ipa_opt_pass
224 pass_ipa_oacc (gcc::context
*ctxt
)
225 : simple_ipa_opt_pass (pass_data_ipa_oacc
, ctxt
)
228 /* opt_pass methods: */
229 virtual bool gate (function
*)
233 /* Don't bother doing anything if the program has errors. */
237 }; // class pass_ipa_oacc
241 simple_ipa_opt_pass
*
242 make_pass_ipa_oacc (gcc::context
*ctxt
)
244 return new pass_ipa_oacc (ctxt
);
247 /* The ipa oacc kernels pass. */
251 const pass_data pass_data_ipa_oacc_kernels
=
253 SIMPLE_IPA_PASS
, /* type */
254 "ipa_oacc_kernels", /* name */
255 OPTGROUP_LOOP
, /* optinfo_flags */
256 TV_TREE_LOOP
, /* tv_id */
257 PROP_cfg
, /* properties_required */
258 0, /* properties_provided */
259 0, /* properties_destroyed */
260 0, /* todo_flags_start */
261 0, /* todo_flags_finish */
264 class pass_ipa_oacc_kernels
: public simple_ipa_opt_pass
267 pass_ipa_oacc_kernels (gcc::context
*ctxt
)
268 : simple_ipa_opt_pass (pass_data_ipa_oacc_kernels
, ctxt
)
271 }; // class pass_ipa_oacc_kernels
275 simple_ipa_opt_pass
*
276 make_pass_ipa_oacc_kernels (gcc::context
*ctxt
)
278 return new pass_ipa_oacc_kernels (ctxt
);
281 /* The no-loop superpass. */
285 const pass_data pass_data_tree_no_loop
=
287 GIMPLE_PASS
, /* type */
288 "no_loop", /* name */
289 OPTGROUP_NONE
, /* optinfo_flags */
290 TV_TREE_NOLOOP
, /* tv_id */
291 PROP_cfg
, /* properties_required */
292 0, /* properties_provided */
293 0, /* properties_destroyed */
294 0, /* todo_flags_start */
295 0, /* todo_flags_finish */
298 class pass_tree_no_loop
: public gimple_opt_pass
301 pass_tree_no_loop (gcc::context
*ctxt
)
302 : gimple_opt_pass (pass_data_tree_no_loop
, ctxt
)
305 /* opt_pass methods: */
306 virtual bool gate (function
*fn
) { return !gate_loop (fn
); }
308 }; // class pass_tree_no_loop
313 make_pass_tree_no_loop (gcc::context
*ctxt
)
315 return new pass_tree_no_loop (ctxt
);
319 /* Loop optimizer initialization. */
323 const pass_data pass_data_tree_loop_init
=
325 GIMPLE_PASS
, /* type */
326 "loopinit", /* name */
327 OPTGROUP_LOOP
, /* optinfo_flags */
329 PROP_cfg
, /* properties_required */
330 0, /* properties_provided */
331 0, /* properties_destroyed */
332 TODO_update_address_taken
, /* todo_flags_start */
333 0, /* todo_flags_finish */
336 class pass_tree_loop_init
: public gimple_opt_pass
339 pass_tree_loop_init (gcc::context
*ctxt
)
340 : gimple_opt_pass (pass_data_tree_loop_init
, ctxt
)
343 /* opt_pass methods: */
344 virtual unsigned int execute (function
*);
346 }; // class pass_tree_loop_init
349 pass_tree_loop_init::execute (function
*fun ATTRIBUTE_UNUSED
)
351 /* When processing a loop in the loop pipeline, we should be able to assert
353 (loops_state_satisfies_p (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS
355 && scev_initialized_p ())
357 loop_optimizer_init (LOOPS_NORMAL
358 | LOOPS_HAVE_RECORDED_EXITS
);
359 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
368 make_pass_tree_loop_init (gcc::context
*ctxt
)
370 return new pass_tree_loop_init (ctxt
);
373 /* Propagation of constants using scev. */
377 const pass_data pass_data_scev_cprop
=
379 GIMPLE_PASS
, /* type */
381 OPTGROUP_LOOP
, /* optinfo_flags */
382 TV_SCEV_CONST
, /* tv_id */
383 ( PROP_cfg
| PROP_ssa
), /* properties_required */
384 0, /* properties_provided */
385 0, /* properties_destroyed */
386 0, /* todo_flags_start */
387 0, /* todo_flags_finish */
390 class pass_scev_cprop
: public gimple_opt_pass
393 pass_scev_cprop (gcc::context
*ctxt
)
394 : gimple_opt_pass (pass_data_scev_cprop
, ctxt
)
397 /* opt_pass methods: */
398 virtual bool gate (function
*) { return flag_tree_scev_cprop
; }
399 virtual unsigned int execute (function
*);
401 }; // class pass_scev_cprop
404 pass_scev_cprop::execute (function
*)
408 /* Perform final value replacement in loops, in case the replacement
409 expressions are cheap. */
410 for (auto loop
: loops_list (cfun
, LI_FROM_INNERMOST
))
411 any
|= final_value_replacement_loop (loop
);
413 return any
? TODO_cleanup_cfg
| TODO_update_ssa_only_virtuals
: 0;
419 make_pass_scev_cprop (gcc::context
*ctxt
)
421 return new pass_scev_cprop (ctxt
);
424 /* Induction variable optimizations. */
428 const pass_data pass_data_iv_optimize
=
430 GIMPLE_PASS
, /* type */
432 OPTGROUP_LOOP
, /* optinfo_flags */
433 TV_TREE_LOOP_IVOPTS
, /* tv_id */
434 ( PROP_cfg
| PROP_ssa
), /* properties_required */
435 0, /* properties_provided */
436 0, /* properties_destroyed */
437 0, /* todo_flags_start */
438 TODO_update_ssa
, /* todo_flags_finish */
441 class pass_iv_optimize
: public gimple_opt_pass
444 pass_iv_optimize (gcc::context
*ctxt
)
445 : gimple_opt_pass (pass_data_iv_optimize
, ctxt
)
448 /* opt_pass methods: */
449 virtual bool gate (function
*) { return flag_ivopts
!= 0; }
450 virtual unsigned int execute (function
*);
452 }; // class pass_iv_optimize
455 pass_iv_optimize::execute (function
*fun
)
457 if (number_of_loops (fun
) <= 1)
460 tree_ssa_iv_optimize ();
467 make_pass_iv_optimize (gcc::context
*ctxt
)
469 return new pass_iv_optimize (ctxt
);
472 /* Loop optimizer finalization. */
475 tree_ssa_loop_done (void)
477 free_numbers_of_iterations_estimates (cfun
);
479 loop_optimizer_finalize (cfun
, true);
485 const pass_data pass_data_tree_loop_done
=
487 GIMPLE_PASS
, /* type */
488 "loopdone", /* name */
489 OPTGROUP_LOOP
, /* optinfo_flags */
491 PROP_cfg
, /* properties_required */
492 PROP_loop_opts_done
, /* properties_provided */
493 0, /* properties_destroyed */
494 0, /* todo_flags_start */
495 TODO_cleanup_cfg
, /* todo_flags_finish */
498 class pass_tree_loop_done
: public gimple_opt_pass
501 pass_tree_loop_done (gcc::context
*ctxt
)
502 : gimple_opt_pass (pass_data_tree_loop_done
, ctxt
)
505 /* opt_pass methods: */
506 virtual unsigned int execute (function
*) { return tree_ssa_loop_done (); }
508 }; // class pass_tree_loop_done
513 make_pass_tree_loop_done (gcc::context
*ctxt
)
515 return new pass_tree_loop_done (ctxt
);
518 /* Calls CBCK for each index in memory reference ADDR_P. There are two
519 kinds situations handled; in each of these cases, the memory reference
520 and DATA are passed to the callback:
522 Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
523 pass the pointer to the index to the callback.
525 Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
526 pointer to addr to the callback.
528 If the callback returns false, the whole search stops and false is returned.
529 Otherwise the function returns true after traversing through the whole
530 reference *ADDR_P. */
533 for_each_index (tree
*addr_p
, bool (*cbck
) (tree
, tree
*, void *), void *data
)
537 for (; ; addr_p
= nxt
)
539 switch (TREE_CODE (*addr_p
))
542 return cbck (*addr_p
, addr_p
, data
);
545 nxt
= &TREE_OPERAND (*addr_p
, 0);
546 return cbck (*addr_p
, nxt
, data
);
549 case VIEW_CONVERT_EXPR
:
552 nxt
= &TREE_OPERAND (*addr_p
, 0);
556 /* If the component has varying offset, it behaves like index
558 idx
= &TREE_OPERAND (*addr_p
, 2);
560 && !cbck (*addr_p
, idx
, data
))
563 nxt
= &TREE_OPERAND (*addr_p
, 0);
567 case ARRAY_RANGE_REF
:
568 nxt
= &TREE_OPERAND (*addr_p
, 0);
569 if (!cbck (*addr_p
, &TREE_OPERAND (*addr_p
, 1), data
))
577 gcc_assert (is_gimple_min_invariant (*addr_p
));
581 idx
= &TMR_BASE (*addr_p
);
583 && !cbck (*addr_p
, idx
, data
))
585 idx
= &TMR_INDEX (*addr_p
);
587 && !cbck (*addr_p
, idx
, data
))
589 idx
= &TMR_INDEX2 (*addr_p
);
591 && !cbck (*addr_p
, idx
, data
))
597 || CONSTANT_CLASS_P (*addr_p
))
605 /* The name and the length of the currently generated variable
607 #define MAX_LSM_NAME_LENGTH 40
608 static char lsm_tmp_name
[MAX_LSM_NAME_LENGTH
+ 1];
609 static int lsm_tmp_name_length
;
611 /* Adds S to lsm_tmp_name. */
614 lsm_tmp_name_add (const char *s
)
616 int l
= strlen (s
) + lsm_tmp_name_length
;
617 if (l
> MAX_LSM_NAME_LENGTH
)
620 strcpy (lsm_tmp_name
+ lsm_tmp_name_length
, s
);
621 lsm_tmp_name_length
= l
;
624 /* Stores the name for temporary variable that replaces REF to
628 gen_lsm_tmp_name (tree ref
)
632 switch (TREE_CODE (ref
))
636 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
637 lsm_tmp_name_add ("_");
641 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
645 case VIEW_CONVERT_EXPR
:
646 case ARRAY_RANGE_REF
:
647 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
651 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
652 lsm_tmp_name_add ("_RE");
656 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
657 lsm_tmp_name_add ("_IM");
661 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
662 lsm_tmp_name_add ("_");
663 name
= get_name (TREE_OPERAND (ref
, 1));
666 lsm_tmp_name_add (name
);
670 gen_lsm_tmp_name (TREE_OPERAND (ref
, 0));
671 lsm_tmp_name_add ("_I");
679 name
= get_name (ref
);
682 lsm_tmp_name_add (name
);
686 lsm_tmp_name_add ("S");
690 lsm_tmp_name_add ("R");
700 /* Determines name for temporary variable that replaces REF.
701 The name is accumulated into the lsm_tmp_name variable.
702 N is added to the name of the temporary. */
705 get_lsm_tmp_name (tree ref
, unsigned n
, const char *suffix
)
709 lsm_tmp_name_length
= 0;
710 gen_lsm_tmp_name (ref
);
711 lsm_tmp_name_add ("_lsm");
716 lsm_tmp_name_add (ns
);
719 lsm_tmp_name_add (suffix
);
723 /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */
726 tree_num_loop_insns (class loop
*loop
, eni_weights
*weights
)
728 basic_block
*body
= get_loop_body (loop
);
729 gimple_stmt_iterator gsi
;
730 unsigned size
= 0, i
;
732 for (i
= 0; i
< loop
->num_nodes
; i
++)
733 for (gsi
= gsi_start_bb (body
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
734 size
+= estimate_num_insns (gsi_stmt (gsi
), weights
);