1*38fd1498Szrj /* Loop optimizations over tree-ssa.
2*38fd1498Szrj Copyright (C) 2003-2018 Free Software Foundation, Inc.
3*38fd1498Szrj
4*38fd1498Szrj This file is part of GCC.
5*38fd1498Szrj
6*38fd1498Szrj GCC is free software; you can redistribute it and/or modify it
7*38fd1498Szrj under the terms of the GNU General Public License as published by the
8*38fd1498Szrj Free Software Foundation; either version 3, or (at your option) any
9*38fd1498Szrj later version.
10*38fd1498Szrj
11*38fd1498Szrj GCC is distributed in the hope that it will be useful, but WITHOUT
12*38fd1498Szrj ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13*38fd1498Szrj FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14*38fd1498Szrj for more details.
15*38fd1498Szrj
16*38fd1498Szrj You should have received a copy of the GNU General Public License
17*38fd1498Szrj along with GCC; see the file COPYING3. If not see
18*38fd1498Szrj <http://www.gnu.org/licenses/>. */
19*38fd1498Szrj
20*38fd1498Szrj #include "config.h"
21*38fd1498Szrj #include "system.h"
22*38fd1498Szrj #include "coretypes.h"
23*38fd1498Szrj #include "backend.h"
24*38fd1498Szrj #include "tree.h"
25*38fd1498Szrj #include "gimple.h"
26*38fd1498Szrj #include "tree-pass.h"
27*38fd1498Szrj #include "memmodel.h"
28*38fd1498Szrj #include "tm_p.h"
29*38fd1498Szrj #include "fold-const.h"
30*38fd1498Szrj #include "gimple-iterator.h"
31*38fd1498Szrj #include "tree-ssa-loop-ivopts.h"
32*38fd1498Szrj #include "tree-ssa-loop-manip.h"
33*38fd1498Szrj #include "tree-ssa-loop-niter.h"
34*38fd1498Szrj #include "tree-ssa-loop.h"
35*38fd1498Szrj #include "cfgloop.h"
36*38fd1498Szrj #include "tree-inline.h"
37*38fd1498Szrj #include "tree-scalar-evolution.h"
38*38fd1498Szrj #include "tree-vectorizer.h"
39*38fd1498Szrj #include "omp-general.h"
40*38fd1498Szrj #include "diagnostic-core.h"
41*38fd1498Szrj #include "stringpool.h"
42*38fd1498Szrj #include "attribs.h"
43*38fd1498Szrj
44*38fd1498Szrj
45*38fd1498Szrj /* A pass making sure loops are fixed up. */
46*38fd1498Szrj
47*38fd1498Szrj namespace {
48*38fd1498Szrj
49*38fd1498Szrj const pass_data pass_data_fix_loops =
50*38fd1498Szrj {
51*38fd1498Szrj GIMPLE_PASS, /* type */
52*38fd1498Szrj "fix_loops", /* name */
53*38fd1498Szrj OPTGROUP_LOOP, /* optinfo_flags */
54*38fd1498Szrj TV_TREE_LOOP, /* tv_id */
55*38fd1498Szrj PROP_cfg, /* properties_required */
56*38fd1498Szrj 0, /* properties_provided */
57*38fd1498Szrj 0, /* properties_destroyed */
58*38fd1498Szrj 0, /* todo_flags_start */
59*38fd1498Szrj 0, /* todo_flags_finish */
60*38fd1498Szrj };
61*38fd1498Szrj
62*38fd1498Szrj class pass_fix_loops : public gimple_opt_pass
63*38fd1498Szrj {
64*38fd1498Szrj public:
pass_fix_loops(gcc::context * ctxt)65*38fd1498Szrj pass_fix_loops (gcc::context *ctxt)
66*38fd1498Szrj : gimple_opt_pass (pass_data_fix_loops, ctxt)
67*38fd1498Szrj {}
68*38fd1498Szrj
69*38fd1498Szrj /* opt_pass methods: */
gate(function *)70*38fd1498Szrj virtual bool gate (function *) { return flag_tree_loop_optimize; }
71*38fd1498Szrj
72*38fd1498Szrj virtual unsigned int execute (function *fn);
73*38fd1498Szrj }; // class pass_fix_loops
74*38fd1498Szrj
75*38fd1498Szrj unsigned int
execute(function *)76*38fd1498Szrj pass_fix_loops::execute (function *)
77*38fd1498Szrj {
78*38fd1498Szrj if (loops_state_satisfies_p (LOOPS_NEED_FIXUP))
79*38fd1498Szrj {
80*38fd1498Szrj calculate_dominance_info (CDI_DOMINATORS);
81*38fd1498Szrj fix_loop_structure (NULL);
82*38fd1498Szrj }
83*38fd1498Szrj return 0;
84*38fd1498Szrj }
85*38fd1498Szrj
86*38fd1498Szrj } // anon namespace
87*38fd1498Szrj
88*38fd1498Szrj gimple_opt_pass *
make_pass_fix_loops(gcc::context * ctxt)89*38fd1498Szrj make_pass_fix_loops (gcc::context *ctxt)
90*38fd1498Szrj {
91*38fd1498Szrj return new pass_fix_loops (ctxt);
92*38fd1498Szrj }
93*38fd1498Szrj
94*38fd1498Szrj
95*38fd1498Szrj /* Gate for loop pass group. The group is controlled by -ftree-loop-optimize
96*38fd1498Szrj but we also avoid running it when the IL doesn't contain any loop. */
97*38fd1498Szrj
98*38fd1498Szrj static bool
gate_loop(function * fn)99*38fd1498Szrj gate_loop (function *fn)
100*38fd1498Szrj {
101*38fd1498Szrj if (!flag_tree_loop_optimize)
102*38fd1498Szrj return false;
103*38fd1498Szrj
104*38fd1498Szrj /* For -fdump-passes which runs before loop discovery print the
105*38fd1498Szrj state of -ftree-loop-optimize. */
106*38fd1498Szrj if (!loops_for_fn (fn))
107*38fd1498Szrj return true;
108*38fd1498Szrj
109*38fd1498Szrj return number_of_loops (fn) > 1;
110*38fd1498Szrj }
111*38fd1498Szrj
112*38fd1498Szrj /* The loop superpass. */
113*38fd1498Szrj
114*38fd1498Szrj namespace {
115*38fd1498Szrj
116*38fd1498Szrj const pass_data pass_data_tree_loop =
117*38fd1498Szrj {
118*38fd1498Szrj GIMPLE_PASS, /* type */
119*38fd1498Szrj "loop", /* name */
120*38fd1498Szrj OPTGROUP_LOOP, /* optinfo_flags */
121*38fd1498Szrj TV_TREE_LOOP, /* tv_id */
122*38fd1498Szrj PROP_cfg, /* properties_required */
123*38fd1498Szrj 0, /* properties_provided */
124*38fd1498Szrj 0, /* properties_destroyed */
125*38fd1498Szrj 0, /* todo_flags_start */
126*38fd1498Szrj 0, /* todo_flags_finish */
127*38fd1498Szrj };
128*38fd1498Szrj
129*38fd1498Szrj class pass_tree_loop : public gimple_opt_pass
130*38fd1498Szrj {
131*38fd1498Szrj public:
pass_tree_loop(gcc::context * ctxt)132*38fd1498Szrj pass_tree_loop (gcc::context *ctxt)
133*38fd1498Szrj : gimple_opt_pass (pass_data_tree_loop, ctxt)
134*38fd1498Szrj {}
135*38fd1498Szrj
136*38fd1498Szrj /* opt_pass methods: */
gate(function * fn)137*38fd1498Szrj virtual bool gate (function *fn) { return gate_loop (fn); }
138*38fd1498Szrj
139*38fd1498Szrj }; // class pass_tree_loop
140*38fd1498Szrj
141*38fd1498Szrj } // anon namespace
142*38fd1498Szrj
143*38fd1498Szrj gimple_opt_pass *
make_pass_tree_loop(gcc::context * ctxt)144*38fd1498Szrj make_pass_tree_loop (gcc::context *ctxt)
145*38fd1498Szrj {
146*38fd1498Szrj return new pass_tree_loop (ctxt);
147*38fd1498Szrj }
148*38fd1498Szrj
149*38fd1498Szrj /* Gate for oacc kernels pass group. */
150*38fd1498Szrj
151*38fd1498Szrj static bool
gate_oacc_kernels(function * fn)152*38fd1498Szrj gate_oacc_kernels (function *fn)
153*38fd1498Szrj {
154*38fd1498Szrj if (!flag_openacc)
155*38fd1498Szrj return false;
156*38fd1498Szrj
157*38fd1498Szrj if (!lookup_attribute ("oacc kernels", DECL_ATTRIBUTES (fn->decl)))
158*38fd1498Szrj return false;
159*38fd1498Szrj
160*38fd1498Szrj struct loop *loop;
161*38fd1498Szrj FOR_EACH_LOOP (loop, 0)
162*38fd1498Szrj if (loop->in_oacc_kernels_region)
163*38fd1498Szrj return true;
164*38fd1498Szrj
165*38fd1498Szrj return false;
166*38fd1498Szrj }
167*38fd1498Szrj
168*38fd1498Szrj /* The oacc kernels superpass. */
169*38fd1498Szrj
170*38fd1498Szrj namespace {
171*38fd1498Szrj
172*38fd1498Szrj const pass_data pass_data_oacc_kernels =
173*38fd1498Szrj {
174*38fd1498Szrj GIMPLE_PASS, /* type */
175*38fd1498Szrj "oacc_kernels", /* name */
176*38fd1498Szrj OPTGROUP_LOOP, /* optinfo_flags */
177*38fd1498Szrj TV_TREE_LOOP, /* tv_id */
178*38fd1498Szrj PROP_cfg, /* properties_required */
179*38fd1498Szrj 0, /* properties_provided */
180*38fd1498Szrj 0, /* properties_destroyed */
181*38fd1498Szrj 0, /* todo_flags_start */
182*38fd1498Szrj 0, /* todo_flags_finish */
183*38fd1498Szrj };
184*38fd1498Szrj
185*38fd1498Szrj class pass_oacc_kernels : public gimple_opt_pass
186*38fd1498Szrj {
187*38fd1498Szrj public:
pass_oacc_kernels(gcc::context * ctxt)188*38fd1498Szrj pass_oacc_kernels (gcc::context *ctxt)
189*38fd1498Szrj : gimple_opt_pass (pass_data_oacc_kernels, ctxt)
190*38fd1498Szrj {}
191*38fd1498Szrj
192*38fd1498Szrj /* opt_pass methods: */
gate(function * fn)193*38fd1498Szrj virtual bool gate (function *fn) { return gate_oacc_kernels (fn); }
194*38fd1498Szrj
195*38fd1498Szrj }; // class pass_oacc_kernels
196*38fd1498Szrj
197*38fd1498Szrj } // anon namespace
198*38fd1498Szrj
199*38fd1498Szrj gimple_opt_pass *
make_pass_oacc_kernels(gcc::context * ctxt)200*38fd1498Szrj make_pass_oacc_kernels (gcc::context *ctxt)
201*38fd1498Szrj {
202*38fd1498Szrj return new pass_oacc_kernels (ctxt);
203*38fd1498Szrj }
204*38fd1498Szrj
205*38fd1498Szrj /* The ipa oacc superpass. */
206*38fd1498Szrj
207*38fd1498Szrj namespace {
208*38fd1498Szrj
209*38fd1498Szrj const pass_data pass_data_ipa_oacc =
210*38fd1498Szrj {
211*38fd1498Szrj SIMPLE_IPA_PASS, /* type */
212*38fd1498Szrj "ipa_oacc", /* name */
213*38fd1498Szrj OPTGROUP_LOOP, /* optinfo_flags */
214*38fd1498Szrj TV_TREE_LOOP, /* tv_id */
215*38fd1498Szrj PROP_cfg, /* properties_required */
216*38fd1498Szrj 0, /* properties_provided */
217*38fd1498Szrj 0, /* properties_destroyed */
218*38fd1498Szrj 0, /* todo_flags_start */
219*38fd1498Szrj 0, /* todo_flags_finish */
220*38fd1498Szrj };
221*38fd1498Szrj
222*38fd1498Szrj class pass_ipa_oacc : public simple_ipa_opt_pass
223*38fd1498Szrj {
224*38fd1498Szrj public:
pass_ipa_oacc(gcc::context * ctxt)225*38fd1498Szrj pass_ipa_oacc (gcc::context *ctxt)
226*38fd1498Szrj : simple_ipa_opt_pass (pass_data_ipa_oacc, ctxt)
227*38fd1498Szrj {}
228*38fd1498Szrj
229*38fd1498Szrj /* opt_pass methods: */
gate(function *)230*38fd1498Szrj virtual bool gate (function *)
231*38fd1498Szrj {
232*38fd1498Szrj return (optimize
233*38fd1498Szrj && flag_openacc
234*38fd1498Szrj /* Don't bother doing anything if the program has errors. */
235*38fd1498Szrj && !seen_error ());
236*38fd1498Szrj }
237*38fd1498Szrj
238*38fd1498Szrj }; // class pass_ipa_oacc
239*38fd1498Szrj
240*38fd1498Szrj } // anon namespace
241*38fd1498Szrj
242*38fd1498Szrj simple_ipa_opt_pass *
make_pass_ipa_oacc(gcc::context * ctxt)243*38fd1498Szrj make_pass_ipa_oacc (gcc::context *ctxt)
244*38fd1498Szrj {
245*38fd1498Szrj return new pass_ipa_oacc (ctxt);
246*38fd1498Szrj }
247*38fd1498Szrj
248*38fd1498Szrj /* The ipa oacc kernels pass. */
249*38fd1498Szrj
250*38fd1498Szrj namespace {
251*38fd1498Szrj
252*38fd1498Szrj const pass_data pass_data_ipa_oacc_kernels =
253*38fd1498Szrj {
254*38fd1498Szrj SIMPLE_IPA_PASS, /* type */
255*38fd1498Szrj "ipa_oacc_kernels", /* name */
256*38fd1498Szrj OPTGROUP_LOOP, /* optinfo_flags */
257*38fd1498Szrj TV_TREE_LOOP, /* tv_id */
258*38fd1498Szrj PROP_cfg, /* properties_required */
259*38fd1498Szrj 0, /* properties_provided */
260*38fd1498Szrj 0, /* properties_destroyed */
261*38fd1498Szrj 0, /* todo_flags_start */
262*38fd1498Szrj 0, /* todo_flags_finish */
263*38fd1498Szrj };
264*38fd1498Szrj
265*38fd1498Szrj class pass_ipa_oacc_kernels : public simple_ipa_opt_pass
266*38fd1498Szrj {
267*38fd1498Szrj public:
pass_ipa_oacc_kernels(gcc::context * ctxt)268*38fd1498Szrj pass_ipa_oacc_kernels (gcc::context *ctxt)
269*38fd1498Szrj : simple_ipa_opt_pass (pass_data_ipa_oacc_kernels, ctxt)
270*38fd1498Szrj {}
271*38fd1498Szrj
272*38fd1498Szrj }; // class pass_ipa_oacc_kernels
273*38fd1498Szrj
274*38fd1498Szrj } // anon namespace
275*38fd1498Szrj
276*38fd1498Szrj simple_ipa_opt_pass *
make_pass_ipa_oacc_kernels(gcc::context * ctxt)277*38fd1498Szrj make_pass_ipa_oacc_kernels (gcc::context *ctxt)
278*38fd1498Szrj {
279*38fd1498Szrj return new pass_ipa_oacc_kernels (ctxt);
280*38fd1498Szrj }
281*38fd1498Szrj
282*38fd1498Szrj /* The no-loop superpass. */
283*38fd1498Szrj
284*38fd1498Szrj namespace {
285*38fd1498Szrj
286*38fd1498Szrj const pass_data pass_data_tree_no_loop =
287*38fd1498Szrj {
288*38fd1498Szrj GIMPLE_PASS, /* type */
289*38fd1498Szrj "no_loop", /* name */
290*38fd1498Szrj OPTGROUP_NONE, /* optinfo_flags */
291*38fd1498Szrj TV_TREE_NOLOOP, /* tv_id */
292*38fd1498Szrj PROP_cfg, /* properties_required */
293*38fd1498Szrj 0, /* properties_provided */
294*38fd1498Szrj 0, /* properties_destroyed */
295*38fd1498Szrj 0, /* todo_flags_start */
296*38fd1498Szrj 0, /* todo_flags_finish */
297*38fd1498Szrj };
298*38fd1498Szrj
299*38fd1498Szrj class pass_tree_no_loop : public gimple_opt_pass
300*38fd1498Szrj {
301*38fd1498Szrj public:
pass_tree_no_loop(gcc::context * ctxt)302*38fd1498Szrj pass_tree_no_loop (gcc::context *ctxt)
303*38fd1498Szrj : gimple_opt_pass (pass_data_tree_no_loop, ctxt)
304*38fd1498Szrj {}
305*38fd1498Szrj
306*38fd1498Szrj /* opt_pass methods: */
gate(function * fn)307*38fd1498Szrj virtual bool gate (function *fn) { return !gate_loop (fn); }
308*38fd1498Szrj
309*38fd1498Szrj }; // class pass_tree_no_loop
310*38fd1498Szrj
311*38fd1498Szrj } // anon namespace
312*38fd1498Szrj
313*38fd1498Szrj gimple_opt_pass *
make_pass_tree_no_loop(gcc::context * ctxt)314*38fd1498Szrj make_pass_tree_no_loop (gcc::context *ctxt)
315*38fd1498Szrj {
316*38fd1498Szrj return new pass_tree_no_loop (ctxt);
317*38fd1498Szrj }
318*38fd1498Szrj
319*38fd1498Szrj
320*38fd1498Szrj /* Loop optimizer initialization. */
321*38fd1498Szrj
322*38fd1498Szrj namespace {
323*38fd1498Szrj
324*38fd1498Szrj const pass_data pass_data_tree_loop_init =
325*38fd1498Szrj {
326*38fd1498Szrj GIMPLE_PASS, /* type */
327*38fd1498Szrj "loopinit", /* name */
328*38fd1498Szrj OPTGROUP_LOOP, /* optinfo_flags */
329*38fd1498Szrj TV_NONE, /* tv_id */
330*38fd1498Szrj PROP_cfg, /* properties_required */
331*38fd1498Szrj 0, /* properties_provided */
332*38fd1498Szrj 0, /* properties_destroyed */
333*38fd1498Szrj 0, /* todo_flags_start */
334*38fd1498Szrj 0, /* todo_flags_finish */
335*38fd1498Szrj };
336*38fd1498Szrj
337*38fd1498Szrj class pass_tree_loop_init : public gimple_opt_pass
338*38fd1498Szrj {
339*38fd1498Szrj public:
pass_tree_loop_init(gcc::context * ctxt)340*38fd1498Szrj pass_tree_loop_init (gcc::context *ctxt)
341*38fd1498Szrj : gimple_opt_pass (pass_data_tree_loop_init, ctxt)
342*38fd1498Szrj {}
343*38fd1498Szrj
344*38fd1498Szrj /* opt_pass methods: */
345*38fd1498Szrj virtual unsigned int execute (function *);
346*38fd1498Szrj
347*38fd1498Szrj }; // class pass_tree_loop_init
348*38fd1498Szrj
349*38fd1498Szrj unsigned int
execute(function * fun ATTRIBUTE_UNUSED)350*38fd1498Szrj pass_tree_loop_init::execute (function *fun ATTRIBUTE_UNUSED)
351*38fd1498Szrj {
352*38fd1498Szrj /* When processing a loop in the loop pipeline, we should be able to assert
353*38fd1498Szrj that:
354*38fd1498Szrj (loops_state_satisfies_p (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS
355*38fd1498Szrj | LOOP_CLOSED_SSA)
356*38fd1498Szrj && scev_initialized_p ())
357*38fd1498Szrj */
358*38fd1498Szrj loop_optimizer_init (LOOPS_NORMAL
359*38fd1498Szrj | LOOPS_HAVE_RECORDED_EXITS);
360*38fd1498Szrj rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
361*38fd1498Szrj scev_initialize ();
362*38fd1498Szrj
363*38fd1498Szrj return 0;
364*38fd1498Szrj }
365*38fd1498Szrj
366*38fd1498Szrj } // anon namespace
367*38fd1498Szrj
368*38fd1498Szrj gimple_opt_pass *
make_pass_tree_loop_init(gcc::context * ctxt)369*38fd1498Szrj make_pass_tree_loop_init (gcc::context *ctxt)
370*38fd1498Szrj {
371*38fd1498Szrj return new pass_tree_loop_init (ctxt);
372*38fd1498Szrj }
373*38fd1498Szrj
374*38fd1498Szrj /* Loop autovectorization. */
375*38fd1498Szrj
376*38fd1498Szrj namespace {
377*38fd1498Szrj
378*38fd1498Szrj const pass_data pass_data_vectorize =
379*38fd1498Szrj {
380*38fd1498Szrj GIMPLE_PASS, /* type */
381*38fd1498Szrj "vect", /* name */
382*38fd1498Szrj OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */
383*38fd1498Szrj TV_TREE_VECTORIZATION, /* tv_id */
384*38fd1498Szrj ( PROP_cfg | PROP_ssa ), /* properties_required */
385*38fd1498Szrj 0, /* properties_provided */
386*38fd1498Szrj 0, /* properties_destroyed */
387*38fd1498Szrj 0, /* todo_flags_start */
388*38fd1498Szrj 0, /* todo_flags_finish */
389*38fd1498Szrj };
390*38fd1498Szrj
391*38fd1498Szrj class pass_vectorize : public gimple_opt_pass
392*38fd1498Szrj {
393*38fd1498Szrj public:
pass_vectorize(gcc::context * ctxt)394*38fd1498Szrj pass_vectorize (gcc::context *ctxt)
395*38fd1498Szrj : gimple_opt_pass (pass_data_vectorize, ctxt)
396*38fd1498Szrj {}
397*38fd1498Szrj
398*38fd1498Szrj /* opt_pass methods: */
gate(function * fun)399*38fd1498Szrj virtual bool gate (function *fun)
400*38fd1498Szrj {
401*38fd1498Szrj return flag_tree_loop_vectorize || fun->has_force_vectorize_loops;
402*38fd1498Szrj }
403*38fd1498Szrj
404*38fd1498Szrj virtual unsigned int execute (function *);
405*38fd1498Szrj
406*38fd1498Szrj }; // class pass_vectorize
407*38fd1498Szrj
408*38fd1498Szrj unsigned int
execute(function * fun)409*38fd1498Szrj pass_vectorize::execute (function *fun)
410*38fd1498Szrj {
411*38fd1498Szrj if (number_of_loops (fun) <= 1)
412*38fd1498Szrj return 0;
413*38fd1498Szrj
414*38fd1498Szrj return vectorize_loops ();
415*38fd1498Szrj }
416*38fd1498Szrj
417*38fd1498Szrj } // anon namespace
418*38fd1498Szrj
419*38fd1498Szrj gimple_opt_pass *
make_pass_vectorize(gcc::context * ctxt)420*38fd1498Szrj make_pass_vectorize (gcc::context *ctxt)
421*38fd1498Szrj {
422*38fd1498Szrj return new pass_vectorize (ctxt);
423*38fd1498Szrj }
424*38fd1498Szrj
425*38fd1498Szrj /* Propagation of constants using scev. */
426*38fd1498Szrj
427*38fd1498Szrj namespace {
428*38fd1498Szrj
429*38fd1498Szrj const pass_data pass_data_scev_cprop =
430*38fd1498Szrj {
431*38fd1498Szrj GIMPLE_PASS, /* type */
432*38fd1498Szrj "sccp", /* name */
433*38fd1498Szrj OPTGROUP_LOOP, /* optinfo_flags */
434*38fd1498Szrj TV_SCEV_CONST, /* tv_id */
435*38fd1498Szrj ( PROP_cfg | PROP_ssa ), /* properties_required */
436*38fd1498Szrj 0, /* properties_provided */
437*38fd1498Szrj 0, /* properties_destroyed */
438*38fd1498Szrj 0, /* todo_flags_start */
439*38fd1498Szrj ( TODO_cleanup_cfg
440*38fd1498Szrj | TODO_update_ssa_only_virtuals ), /* todo_flags_finish */
441*38fd1498Szrj };
442*38fd1498Szrj
443*38fd1498Szrj class pass_scev_cprop : public gimple_opt_pass
444*38fd1498Szrj {
445*38fd1498Szrj public:
pass_scev_cprop(gcc::context * ctxt)446*38fd1498Szrj pass_scev_cprop (gcc::context *ctxt)
447*38fd1498Szrj : gimple_opt_pass (pass_data_scev_cprop, ctxt)
448*38fd1498Szrj {}
449*38fd1498Szrj
450*38fd1498Szrj /* opt_pass methods: */
gate(function *)451*38fd1498Szrj virtual bool gate (function *) { return flag_tree_scev_cprop; }
execute(function *)452*38fd1498Szrj virtual unsigned int execute (function *) { return scev_const_prop (); }
453*38fd1498Szrj
454*38fd1498Szrj }; // class pass_scev_cprop
455*38fd1498Szrj
456*38fd1498Szrj } // anon namespace
457*38fd1498Szrj
458*38fd1498Szrj gimple_opt_pass *
make_pass_scev_cprop(gcc::context * ctxt)459*38fd1498Szrj make_pass_scev_cprop (gcc::context *ctxt)
460*38fd1498Szrj {
461*38fd1498Szrj return new pass_scev_cprop (ctxt);
462*38fd1498Szrj }
463*38fd1498Szrj
464*38fd1498Szrj /* Induction variable optimizations. */
465*38fd1498Szrj
466*38fd1498Szrj namespace {
467*38fd1498Szrj
468*38fd1498Szrj const pass_data pass_data_iv_optimize =
469*38fd1498Szrj {
470*38fd1498Szrj GIMPLE_PASS, /* type */
471*38fd1498Szrj "ivopts", /* name */
472*38fd1498Szrj OPTGROUP_LOOP, /* optinfo_flags */
473*38fd1498Szrj TV_TREE_LOOP_IVOPTS, /* tv_id */
474*38fd1498Szrj ( PROP_cfg | PROP_ssa ), /* properties_required */
475*38fd1498Szrj 0, /* properties_provided */
476*38fd1498Szrj 0, /* properties_destroyed */
477*38fd1498Szrj 0, /* todo_flags_start */
478*38fd1498Szrj TODO_update_ssa, /* todo_flags_finish */
479*38fd1498Szrj };
480*38fd1498Szrj
481*38fd1498Szrj class pass_iv_optimize : public gimple_opt_pass
482*38fd1498Szrj {
483*38fd1498Szrj public:
pass_iv_optimize(gcc::context * ctxt)484*38fd1498Szrj pass_iv_optimize (gcc::context *ctxt)
485*38fd1498Szrj : gimple_opt_pass (pass_data_iv_optimize, ctxt)
486*38fd1498Szrj {}
487*38fd1498Szrj
488*38fd1498Szrj /* opt_pass methods: */
gate(function *)489*38fd1498Szrj virtual bool gate (function *) { return flag_ivopts != 0; }
490*38fd1498Szrj virtual unsigned int execute (function *);
491*38fd1498Szrj
492*38fd1498Szrj }; // class pass_iv_optimize
493*38fd1498Szrj
494*38fd1498Szrj unsigned int
execute(function * fun)495*38fd1498Szrj pass_iv_optimize::execute (function *fun)
496*38fd1498Szrj {
497*38fd1498Szrj if (number_of_loops (fun) <= 1)
498*38fd1498Szrj return 0;
499*38fd1498Szrj
500*38fd1498Szrj tree_ssa_iv_optimize ();
501*38fd1498Szrj return 0;
502*38fd1498Szrj }
503*38fd1498Szrj
504*38fd1498Szrj } // anon namespace
505*38fd1498Szrj
506*38fd1498Szrj gimple_opt_pass *
make_pass_iv_optimize(gcc::context * ctxt)507*38fd1498Szrj make_pass_iv_optimize (gcc::context *ctxt)
508*38fd1498Szrj {
509*38fd1498Szrj return new pass_iv_optimize (ctxt);
510*38fd1498Szrj }
511*38fd1498Szrj
512*38fd1498Szrj /* Loop optimizer finalization. */
513*38fd1498Szrj
514*38fd1498Szrj static unsigned int
tree_ssa_loop_done(void)515*38fd1498Szrj tree_ssa_loop_done (void)
516*38fd1498Szrj {
517*38fd1498Szrj free_numbers_of_iterations_estimates (cfun);
518*38fd1498Szrj scev_finalize ();
519*38fd1498Szrj loop_optimizer_finalize ();
520*38fd1498Szrj return 0;
521*38fd1498Szrj }
522*38fd1498Szrj
523*38fd1498Szrj namespace {
524*38fd1498Szrj
525*38fd1498Szrj const pass_data pass_data_tree_loop_done =
526*38fd1498Szrj {
527*38fd1498Szrj GIMPLE_PASS, /* type */
528*38fd1498Szrj "loopdone", /* name */
529*38fd1498Szrj OPTGROUP_LOOP, /* optinfo_flags */
530*38fd1498Szrj TV_NONE, /* tv_id */
531*38fd1498Szrj PROP_cfg, /* properties_required */
532*38fd1498Szrj 0, /* properties_provided */
533*38fd1498Szrj 0, /* properties_destroyed */
534*38fd1498Szrj 0, /* todo_flags_start */
535*38fd1498Szrj TODO_cleanup_cfg, /* todo_flags_finish */
536*38fd1498Szrj };
537*38fd1498Szrj
538*38fd1498Szrj class pass_tree_loop_done : public gimple_opt_pass
539*38fd1498Szrj {
540*38fd1498Szrj public:
pass_tree_loop_done(gcc::context * ctxt)541*38fd1498Szrj pass_tree_loop_done (gcc::context *ctxt)
542*38fd1498Szrj : gimple_opt_pass (pass_data_tree_loop_done, ctxt)
543*38fd1498Szrj {}
544*38fd1498Szrj
545*38fd1498Szrj /* opt_pass methods: */
execute(function *)546*38fd1498Szrj virtual unsigned int execute (function *) { return tree_ssa_loop_done (); }
547*38fd1498Szrj
548*38fd1498Szrj }; // class pass_tree_loop_done
549*38fd1498Szrj
550*38fd1498Szrj } // anon namespace
551*38fd1498Szrj
552*38fd1498Szrj gimple_opt_pass *
make_pass_tree_loop_done(gcc::context * ctxt)553*38fd1498Szrj make_pass_tree_loop_done (gcc::context *ctxt)
554*38fd1498Szrj {
555*38fd1498Szrj return new pass_tree_loop_done (ctxt);
556*38fd1498Szrj }
557*38fd1498Szrj
558*38fd1498Szrj /* Calls CBCK for each index in memory reference ADDR_P. There are two
559*38fd1498Szrj kinds situations handled; in each of these cases, the memory reference
560*38fd1498Szrj and DATA are passed to the callback:
561*38fd1498Szrj
562*38fd1498Szrj Access to an array: ARRAY_{RANGE_}REF (base, index). In this case we also
563*38fd1498Szrj pass the pointer to the index to the callback.
564*38fd1498Szrj
565*38fd1498Szrj Pointer dereference: INDIRECT_REF (addr). In this case we also pass the
566*38fd1498Szrj pointer to addr to the callback.
567*38fd1498Szrj
568*38fd1498Szrj If the callback returns false, the whole search stops and false is returned.
569*38fd1498Szrj Otherwise the function returns true after traversing through the whole
570*38fd1498Szrj reference *ADDR_P. */
571*38fd1498Szrj
572*38fd1498Szrj bool
for_each_index(tree * addr_p,bool (* cbck)(tree,tree *,void *),void * data)573*38fd1498Szrj for_each_index (tree *addr_p, bool (*cbck) (tree, tree *, void *), void *data)
574*38fd1498Szrj {
575*38fd1498Szrj tree *nxt, *idx;
576*38fd1498Szrj
577*38fd1498Szrj for (; ; addr_p = nxt)
578*38fd1498Szrj {
579*38fd1498Szrj switch (TREE_CODE (*addr_p))
580*38fd1498Szrj {
581*38fd1498Szrj case SSA_NAME:
582*38fd1498Szrj return cbck (*addr_p, addr_p, data);
583*38fd1498Szrj
584*38fd1498Szrj case MEM_REF:
585*38fd1498Szrj nxt = &TREE_OPERAND (*addr_p, 0);
586*38fd1498Szrj return cbck (*addr_p, nxt, data);
587*38fd1498Szrj
588*38fd1498Szrj case BIT_FIELD_REF:
589*38fd1498Szrj case VIEW_CONVERT_EXPR:
590*38fd1498Szrj case REALPART_EXPR:
591*38fd1498Szrj case IMAGPART_EXPR:
592*38fd1498Szrj nxt = &TREE_OPERAND (*addr_p, 0);
593*38fd1498Szrj break;
594*38fd1498Szrj
595*38fd1498Szrj case COMPONENT_REF:
596*38fd1498Szrj /* If the component has varying offset, it behaves like index
597*38fd1498Szrj as well. */
598*38fd1498Szrj idx = &TREE_OPERAND (*addr_p, 2);
599*38fd1498Szrj if (*idx
600*38fd1498Szrj && !cbck (*addr_p, idx, data))
601*38fd1498Szrj return false;
602*38fd1498Szrj
603*38fd1498Szrj nxt = &TREE_OPERAND (*addr_p, 0);
604*38fd1498Szrj break;
605*38fd1498Szrj
606*38fd1498Szrj case ARRAY_REF:
607*38fd1498Szrj case ARRAY_RANGE_REF:
608*38fd1498Szrj nxt = &TREE_OPERAND (*addr_p, 0);
609*38fd1498Szrj if (!cbck (*addr_p, &TREE_OPERAND (*addr_p, 1), data))
610*38fd1498Szrj return false;
611*38fd1498Szrj break;
612*38fd1498Szrj
613*38fd1498Szrj case VAR_DECL:
614*38fd1498Szrj case PARM_DECL:
615*38fd1498Szrj case CONST_DECL:
616*38fd1498Szrj case STRING_CST:
617*38fd1498Szrj case RESULT_DECL:
618*38fd1498Szrj case VECTOR_CST:
619*38fd1498Szrj case COMPLEX_CST:
620*38fd1498Szrj case INTEGER_CST:
621*38fd1498Szrj case POLY_INT_CST:
622*38fd1498Szrj case REAL_CST:
623*38fd1498Szrj case FIXED_CST:
624*38fd1498Szrj case CONSTRUCTOR:
625*38fd1498Szrj return true;
626*38fd1498Szrj
627*38fd1498Szrj case ADDR_EXPR:
628*38fd1498Szrj gcc_assert (is_gimple_min_invariant (*addr_p));
629*38fd1498Szrj return true;
630*38fd1498Szrj
631*38fd1498Szrj case TARGET_MEM_REF:
632*38fd1498Szrj idx = &TMR_BASE (*addr_p);
633*38fd1498Szrj if (*idx
634*38fd1498Szrj && !cbck (*addr_p, idx, data))
635*38fd1498Szrj return false;
636*38fd1498Szrj idx = &TMR_INDEX (*addr_p);
637*38fd1498Szrj if (*idx
638*38fd1498Szrj && !cbck (*addr_p, idx, data))
639*38fd1498Szrj return false;
640*38fd1498Szrj idx = &TMR_INDEX2 (*addr_p);
641*38fd1498Szrj if (*idx
642*38fd1498Szrj && !cbck (*addr_p, idx, data))
643*38fd1498Szrj return false;
644*38fd1498Szrj return true;
645*38fd1498Szrj
646*38fd1498Szrj default:
647*38fd1498Szrj gcc_unreachable ();
648*38fd1498Szrj }
649*38fd1498Szrj }
650*38fd1498Szrj }
651*38fd1498Szrj
652*38fd1498Szrj
653*38fd1498Szrj /* The name and the length of the currently generated variable
654*38fd1498Szrj for lsm. */
655*38fd1498Szrj #define MAX_LSM_NAME_LENGTH 40
656*38fd1498Szrj static char lsm_tmp_name[MAX_LSM_NAME_LENGTH + 1];
657*38fd1498Szrj static int lsm_tmp_name_length;
658*38fd1498Szrj
659*38fd1498Szrj /* Adds S to lsm_tmp_name. */
660*38fd1498Szrj
661*38fd1498Szrj static void
lsm_tmp_name_add(const char * s)662*38fd1498Szrj lsm_tmp_name_add (const char *s)
663*38fd1498Szrj {
664*38fd1498Szrj int l = strlen (s) + lsm_tmp_name_length;
665*38fd1498Szrj if (l > MAX_LSM_NAME_LENGTH)
666*38fd1498Szrj return;
667*38fd1498Szrj
668*38fd1498Szrj strcpy (lsm_tmp_name + lsm_tmp_name_length, s);
669*38fd1498Szrj lsm_tmp_name_length = l;
670*38fd1498Szrj }
671*38fd1498Szrj
672*38fd1498Szrj /* Stores the name for temporary variable that replaces REF to
673*38fd1498Szrj lsm_tmp_name. */
674*38fd1498Szrj
675*38fd1498Szrj static void
gen_lsm_tmp_name(tree ref)676*38fd1498Szrj gen_lsm_tmp_name (tree ref)
677*38fd1498Szrj {
678*38fd1498Szrj const char *name;
679*38fd1498Szrj
680*38fd1498Szrj switch (TREE_CODE (ref))
681*38fd1498Szrj {
682*38fd1498Szrj case MEM_REF:
683*38fd1498Szrj case TARGET_MEM_REF:
684*38fd1498Szrj gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
685*38fd1498Szrj lsm_tmp_name_add ("_");
686*38fd1498Szrj break;
687*38fd1498Szrj
688*38fd1498Szrj case ADDR_EXPR:
689*38fd1498Szrj gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
690*38fd1498Szrj break;
691*38fd1498Szrj
692*38fd1498Szrj case BIT_FIELD_REF:
693*38fd1498Szrj case VIEW_CONVERT_EXPR:
694*38fd1498Szrj case ARRAY_RANGE_REF:
695*38fd1498Szrj gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
696*38fd1498Szrj break;
697*38fd1498Szrj
698*38fd1498Szrj case REALPART_EXPR:
699*38fd1498Szrj gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
700*38fd1498Szrj lsm_tmp_name_add ("_RE");
701*38fd1498Szrj break;
702*38fd1498Szrj
703*38fd1498Szrj case IMAGPART_EXPR:
704*38fd1498Szrj gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
705*38fd1498Szrj lsm_tmp_name_add ("_IM");
706*38fd1498Szrj break;
707*38fd1498Szrj
708*38fd1498Szrj case COMPONENT_REF:
709*38fd1498Szrj gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
710*38fd1498Szrj lsm_tmp_name_add ("_");
711*38fd1498Szrj name = get_name (TREE_OPERAND (ref, 1));
712*38fd1498Szrj if (!name)
713*38fd1498Szrj name = "F";
714*38fd1498Szrj lsm_tmp_name_add (name);
715*38fd1498Szrj break;
716*38fd1498Szrj
717*38fd1498Szrj case ARRAY_REF:
718*38fd1498Szrj gen_lsm_tmp_name (TREE_OPERAND (ref, 0));
719*38fd1498Szrj lsm_tmp_name_add ("_I");
720*38fd1498Szrj break;
721*38fd1498Szrj
722*38fd1498Szrj case SSA_NAME:
723*38fd1498Szrj case VAR_DECL:
724*38fd1498Szrj case PARM_DECL:
725*38fd1498Szrj case FUNCTION_DECL:
726*38fd1498Szrj case LABEL_DECL:
727*38fd1498Szrj name = get_name (ref);
728*38fd1498Szrj if (!name)
729*38fd1498Szrj name = "D";
730*38fd1498Szrj lsm_tmp_name_add (name);
731*38fd1498Szrj break;
732*38fd1498Szrj
733*38fd1498Szrj case STRING_CST:
734*38fd1498Szrj lsm_tmp_name_add ("S");
735*38fd1498Szrj break;
736*38fd1498Szrj
737*38fd1498Szrj case RESULT_DECL:
738*38fd1498Szrj lsm_tmp_name_add ("R");
739*38fd1498Szrj break;
740*38fd1498Szrj
741*38fd1498Szrj case INTEGER_CST:
742*38fd1498Szrj default:
743*38fd1498Szrj /* Nothing. */
744*38fd1498Szrj break;
745*38fd1498Szrj }
746*38fd1498Szrj }
747*38fd1498Szrj
748*38fd1498Szrj /* Determines name for temporary variable that replaces REF.
749*38fd1498Szrj The name is accumulated into the lsm_tmp_name variable.
750*38fd1498Szrj N is added to the name of the temporary. */
751*38fd1498Szrj
752*38fd1498Szrj char *
get_lsm_tmp_name(tree ref,unsigned n,const char * suffix)753*38fd1498Szrj get_lsm_tmp_name (tree ref, unsigned n, const char *suffix)
754*38fd1498Szrj {
755*38fd1498Szrj char ns[2];
756*38fd1498Szrj
757*38fd1498Szrj lsm_tmp_name_length = 0;
758*38fd1498Szrj gen_lsm_tmp_name (ref);
759*38fd1498Szrj lsm_tmp_name_add ("_lsm");
760*38fd1498Szrj if (n < 10)
761*38fd1498Szrj {
762*38fd1498Szrj ns[0] = '0' + n;
763*38fd1498Szrj ns[1] = 0;
764*38fd1498Szrj lsm_tmp_name_add (ns);
765*38fd1498Szrj }
766*38fd1498Szrj return lsm_tmp_name;
767*38fd1498Szrj if (suffix != NULL)
768*38fd1498Szrj lsm_tmp_name_add (suffix);
769*38fd1498Szrj }
770*38fd1498Szrj
771*38fd1498Szrj /* Computes an estimated number of insns in LOOP, weighted by WEIGHTS. */
772*38fd1498Szrj
773*38fd1498Szrj unsigned
tree_num_loop_insns(struct loop * loop,eni_weights * weights)774*38fd1498Szrj tree_num_loop_insns (struct loop *loop, eni_weights *weights)
775*38fd1498Szrj {
776*38fd1498Szrj basic_block *body = get_loop_body (loop);
777*38fd1498Szrj gimple_stmt_iterator gsi;
778*38fd1498Szrj unsigned size = 0, i;
779*38fd1498Szrj
780*38fd1498Szrj for (i = 0; i < loop->num_nodes; i++)
781*38fd1498Szrj for (gsi = gsi_start_bb (body[i]); !gsi_end_p (gsi); gsi_next (&gsi))
782*38fd1498Szrj size += estimate_num_insns (gsi_stmt (gsi), weights);
783*38fd1498Szrj free (body);
784*38fd1498Szrj
785*38fd1498Szrj return size;
786*38fd1498Szrj }
787*38fd1498Szrj
788*38fd1498Szrj
789*38fd1498Szrj
790