]>
Commit | Line | Data |
---|---|---|
16207ddd | 1 | /* Support routines for Value Range Propagation (VRP). |
99dee823 | 2 | Copyright (C) 2005-2021 Free Software Foundation, Inc. |
16207ddd JL |
3 | |
4 | This file is part of GCC. | |
5 | ||
6 | GCC is free software; you can redistribute it and/or modify | |
7 | it under the terms of the GNU General Public License as published by | |
8 | the Free Software Foundation; either version 3, or (at your option) | |
9 | any later version. | |
10 | ||
11 | GCC is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | GNU General Public License for more details. | |
15 | ||
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/>. */ | |
19 | ||
20 | #include "config.h" | |
21 | #include "system.h" | |
22 | #include "coretypes.h" | |
23 | #include "backend.h" | |
24 | #include "tree.h" | |
25 | #include "gimple.h" | |
26 | #include "tree-pass.h" | |
27 | #include "ssa.h" | |
28 | #include "gimple-pretty-print.h" | |
29 | #include "cfganal.h" | |
30 | #include "gimple-fold.h" | |
31 | #include "tree-eh.h" | |
32 | #include "gimple-iterator.h" | |
33 | #include "tree-cfg.h" | |
34 | #include "tree-ssa-loop-manip.h" | |
35 | #include "tree-ssa-loop.h" | |
36 | #include "cfgloop.h" | |
37 | #include "tree-scalar-evolution.h" | |
38 | #include "tree-ssa-propagate.h" | |
39 | #include "alloc-pool.h" | |
40 | #include "domwalk.h" | |
41 | #include "tree-cfgcleanup.h" | |
42 | #include "vr-values.h" | |
74ba745b | 43 | #include "gimple-ssa-evrp-analyze.h" |
fcae5121 AM |
44 | #include "gimple-range.h" |
45 | ||
46 | // This is the classic EVRP folder which uses a dominator walk and pushes | |
47 | // ranges into the next block if it is a single predecessor block. | |
16207ddd JL |
48 | |
49 | class evrp_folder : public substitute_and_fold_engine | |
16207ddd JL |
50 | { |
51 | public: | |
a889e06a AH |
52 | evrp_folder () : |
53 | substitute_and_fold_engine (), | |
54 | m_range_analyzer (/*update_global_ranges=*/true), | |
55 | simplifier (&m_range_analyzer) | |
56 | { } | |
1396fa5b AH |
57 | |
58 | ~evrp_folder () | |
59 | { | |
1396fa5b AH |
60 | if (dump_file) |
61 | { | |
62 | fprintf (dump_file, "\nValue ranges after Early VRP:\n\n"); | |
586d6f7a | 63 | m_range_analyzer.dump (dump_file); |
1396fa5b AH |
64 | fprintf (dump_file, "\n"); |
65 | } | |
66 | } | |
67 | ||
a889e06a | 68 | tree value_of_expr (tree name, gimple *stmt) OVERRIDE |
1396fa5b | 69 | { |
a889e06a | 70 | return m_range_analyzer.value_of_expr (name, stmt); |
1396fa5b AH |
71 | } |
72 | ||
73 | void pre_fold_bb (basic_block bb) OVERRIDE | |
74 | { | |
75 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
76 | fprintf (dump_file, "evrp visiting BB%d\n", bb->index); | |
77 | m_range_analyzer.enter (bb); | |
78 | } | |
79 | ||
80 | void pre_fold_stmt (gimple *stmt) OVERRIDE | |
81 | { | |
82 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
83 | { | |
84 | fprintf (dump_file, "evrp visiting stmt "); | |
85 | print_gimple_stmt (dump_file, stmt, 0); | |
86 | } | |
87 | m_range_analyzer.record_ranges_from_stmt (stmt, false); | |
88 | } | |
89 | ||
90 | bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE | |
91 | { | |
fc36b97a | 92 | return simplifier.simplify (gsi); |
1396fa5b AH |
93 | } |
94 | ||
95 | void post_fold_bb (basic_block bb) OVERRIDE | |
96 | { | |
97 | m_range_analyzer.leave (bb); | |
98 | } | |
99 | ||
100 | void post_new_stmt (gimple *stmt) OVERRIDE | |
101 | { | |
a889e06a | 102 | m_range_analyzer.set_defs_to_varying (stmt); |
1396fa5b AH |
103 | } |
104 | ||
fcae5121 | 105 | protected: |
1396fa5b | 106 | DISABLE_COPY_AND_ASSIGN (evrp_folder); |
a889e06a | 107 | evrp_range_analyzer m_range_analyzer; |
fc36b97a | 108 | simplify_using_ranges simplifier; |
16207ddd JL |
109 | }; |
110 | ||
fcae5121 AM |
111 | // This is a ranger based folder which continues to use the dominator |
112 | // walk to access the substitute and fold machinery. Ranges are calculated | |
113 | // on demand. | |
114 | ||
115 | class rvrp_folder : public substitute_and_fold_engine | |
116 | { | |
117 | public: | |
118 | ||
119 | rvrp_folder () : substitute_and_fold_engine (), m_simplifier () | |
120 | { | |
1e247c60 | 121 | if (param_evrp_mode & EVRP_MODE_TRACE) |
fcae5121 AM |
122 | m_ranger = new trace_ranger (); |
123 | else | |
124 | m_ranger = new gimple_ranger (); | |
125 | m_simplifier.set_range_query (m_ranger); | |
126 | } | |
127 | ||
128 | ~rvrp_folder () | |
129 | { | |
130 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
131 | m_ranger->dump (dump_file); | |
132 | delete m_ranger; | |
133 | } | |
134 | ||
135 | tree value_of_expr (tree name, gimple *s = NULL) OVERRIDE | |
136 | { | |
137 | return m_ranger->value_of_expr (name, s); | |
138 | } | |
139 | ||
140 | tree value_on_edge (edge e, tree name) OVERRIDE | |
141 | { | |
142 | return m_ranger->value_on_edge (e, name); | |
143 | } | |
144 | ||
145 | tree value_of_stmt (gimple *s, tree name = NULL) OVERRIDE | |
146 | { | |
147 | return m_ranger->value_of_stmt (s, name); | |
148 | } | |
149 | ||
150 | bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE | |
151 | { | |
152 | return m_simplifier.simplify (gsi); | |
153 | } | |
154 | ||
155 | private: | |
156 | DISABLE_COPY_AND_ASSIGN (rvrp_folder); | |
157 | gimple_ranger *m_ranger; | |
158 | simplify_using_ranges m_simplifier; | |
159 | }; | |
160 | ||
161 | // In a hybrid folder, start with an EVRP folder, and add the required | |
162 | // fold_stmt bits to either try the ranger first or second. | |
163 | // | |
164 | // The 3 value_* routines will always query both EVRP and the ranger for | |
165 | // a result, and ensure they return the same value. If either returns a value | |
166 | // when the other doesn't, it is flagged in the listing, and the discoverd | |
167 | // value is returned. | |
168 | // | |
169 | // The simplifier is unable to process 2 different sources, thus we try to | |
170 | // use one engine, and if it fails to simplify, try using the other engine. | |
171 | // It is reported when the first attempt fails and the second succeeds. | |
172 | ||
173 | class hybrid_folder : public evrp_folder | |
174 | { | |
175 | public: | |
176 | hybrid_folder (bool evrp_first) | |
177 | { | |
1e247c60 | 178 | if (param_evrp_mode & EVRP_MODE_TRACE) |
fcae5121 AM |
179 | m_ranger = new trace_ranger (); |
180 | else | |
181 | m_ranger = new gimple_ranger (); | |
182 | ||
183 | if (evrp_first) | |
184 | { | |
185 | first = &m_range_analyzer; | |
186 | second = m_ranger; | |
187 | } | |
188 | else | |
189 | { | |
190 | first = m_ranger; | |
191 | second = &m_range_analyzer; | |
192 | } | |
193 | } | |
194 | ||
195 | ~hybrid_folder () | |
196 | { | |
197 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
198 | m_ranger->dump (dump_file); | |
199 | delete m_ranger; | |
200 | } | |
201 | ||
202 | bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE | |
203 | { | |
204 | simplifier.set_range_query (first); | |
205 | if (simplifier.simplify (gsi)) | |
206 | return true; | |
207 | ||
208 | simplifier.set_range_query (second); | |
209 | if (simplifier.simplify (gsi)) | |
210 | { | |
211 | if (dump_file) | |
212 | fprintf (dump_file, "EVRP:hybrid: Second query simplifed stmt\n"); | |
213 | return true; | |
214 | } | |
215 | return false; | |
216 | } | |
217 | ||
218 | tree value_of_expr (tree name, gimple *) OVERRIDE; | |
219 | tree value_on_edge (edge, tree name) OVERRIDE; | |
220 | tree value_of_stmt (gimple *, tree name) OVERRIDE; | |
221 | ||
222 | private: | |
223 | DISABLE_COPY_AND_ASSIGN (hybrid_folder); | |
224 | gimple_ranger *m_ranger; | |
225 | range_query *first; | |
226 | range_query *second; | |
227 | tree choose_value (tree evrp_val, tree ranger_val); | |
228 | }; | |
229 | ||
230 | ||
231 | tree | |
232 | hybrid_folder::value_of_expr (tree op, gimple *stmt) | |
233 | { | |
234 | tree evrp_ret = evrp_folder::value_of_expr (op, stmt); | |
235 | tree ranger_ret = m_ranger->value_of_expr (op, stmt); | |
236 | return choose_value (evrp_ret, ranger_ret); | |
237 | } | |
238 | ||
239 | tree | |
240 | hybrid_folder::value_on_edge (edge e, tree op) | |
241 | { | |
aabc96c9 AM |
242 | // Call evrp::value_of_expr directly. Otherwise another dual call is made |
243 | // via hybrid_folder::value_of_expr, but without an edge. | |
244 | tree evrp_ret = evrp_folder::value_of_expr (op, NULL); | |
fcae5121 AM |
245 | tree ranger_ret = m_ranger->value_on_edge (e, op); |
246 | return choose_value (evrp_ret, ranger_ret); | |
247 | } | |
248 | ||
249 | tree | |
250 | hybrid_folder::value_of_stmt (gimple *stmt, tree op) | |
251 | { | |
aabc96c9 AM |
252 | // Call evrp::value_of_expr directly. Otherwise another dual call is made |
253 | // via hybrid_folder::value_of_expr, but without a stmt. | |
254 | tree evrp_ret; | |
255 | if (op) | |
256 | evrp_ret = evrp_folder::value_of_expr (op, NULL); | |
257 | else | |
258 | evrp_ret = NULL_TREE; | |
259 | ||
fcae5121 AM |
260 | tree ranger_ret = m_ranger->value_of_stmt (stmt, op); |
261 | return choose_value (evrp_ret, ranger_ret); | |
262 | } | |
263 | ||
264 | // Given trees returned by EVRP and Ranger, choose/report the value to use | |
265 | // by the folder. | |
266 | ||
267 | tree | |
268 | hybrid_folder::choose_value (tree evrp_val, tree ranger_val) | |
269 | { | |
214d514f AH |
270 | // If both found the same value, just return it. |
271 | if (evrp_val && ranger_val && !compare_values (evrp_val, ranger_val)) | |
272 | return evrp_val; | |
273 | ||
274 | // If neither returned a value, return NULL_TREE. | |
275 | if (!ranger_val && !evrp_val) | |
276 | return NULL_TREE; | |
fcae5121 | 277 | |
214d514f AH |
278 | // Otherwise there is a discrepancy to flag. |
279 | if (dump_file) | |
280 | { | |
281 | if (evrp_val && ranger_val) | |
282 | fprintf (dump_file, "EVRP:hybrid: Disagreement\n"); | |
283 | if (evrp_val) | |
fcae5121 AM |
284 | { |
285 | fprintf (dump_file, "EVRP:hybrid: EVRP found singleton "); | |
286 | print_generic_expr (dump_file, evrp_val); | |
287 | fprintf (dump_file, "\n"); | |
288 | } | |
214d514f AH |
289 | if (ranger_val) |
290 | { | |
291 | fprintf (dump_file, "EVRP:hybrid: RVRP found singleton "); | |
292 | print_generic_expr (dump_file, ranger_val); | |
293 | fprintf (dump_file, "\n"); | |
294 | } | |
fcae5121 AM |
295 | } |
296 | ||
214d514f AH |
297 | // If one value was found, return it. |
298 | if (!evrp_val) | |
299 | return ranger_val; | |
300 | if (!ranger_val) | |
fcae5121 AM |
301 | return evrp_val; |
302 | ||
214d514f AH |
303 | // If values are different, return the first calculated value. |
304 | if ((param_evrp_mode & EVRP_MODE_RVRP_FIRST) == EVRP_MODE_RVRP_FIRST) | |
305 | return ranger_val; | |
306 | return evrp_val; | |
fcae5121 AM |
307 | } |
308 | ||
271eeb18 JL |
309 | /* Main entry point for the early vrp pass which is a simplified non-iterative |
310 | version of vrp where basic blocks are visited in dominance order. Value | |
311 | ranges discovered in early vrp will also be used by ipa-vrp. */ | |
312 | ||
313 | static unsigned int | |
314 | execute_early_vrp () | |
315 | { | |
1396fa5b AH |
316 | /* Ideally this setup code would move into the ctor for the folder |
317 | However, this setup can change the number of blocks which | |
271eeb18 | 318 | invalidates the internal arrays that are set up by the dominator |
1396fa5b | 319 | walker in substitute_and_fold_engine. */ |
271eeb18 JL |
320 | loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS); |
321 | rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); | |
322 | scev_initialize (); | |
323 | calculate_dominance_info (CDI_DOMINATORS); | |
271eeb18 | 324 | |
1e247c60 AH |
325 | // Only the last 2 bits matter for choosing the folder. |
326 | switch (param_evrp_mode & EVRP_MODE_RVRP_FIRST) | |
fcae5121 AM |
327 | { |
328 | case EVRP_MODE_EVRP_ONLY: | |
329 | { | |
330 | evrp_folder folder; | |
331 | folder.substitute_and_fold (); | |
332 | break; | |
333 | } | |
334 | case EVRP_MODE_RVRP_ONLY: | |
335 | { | |
336 | rvrp_folder folder; | |
337 | folder.substitute_and_fold (); | |
338 | break; | |
339 | } | |
340 | case EVRP_MODE_EVRP_FIRST: | |
341 | { | |
342 | hybrid_folder folder (true); | |
343 | folder.substitute_and_fold (); | |
344 | break; | |
345 | } | |
346 | case EVRP_MODE_RVRP_FIRST: | |
347 | { | |
348 | hybrid_folder folder (false); | |
349 | folder.substitute_and_fold (); | |
350 | break; | |
351 | } | |
352 | default: | |
353 | gcc_unreachable (); | |
354 | } | |
16207ddd JL |
355 | |
356 | scev_finalize (); | |
357 | loop_optimizer_finalize (); | |
358 | return 0; | |
359 | } | |
360 | ||
361 | namespace { | |
362 | ||
363 | const pass_data pass_data_early_vrp = | |
364 | { | |
365 | GIMPLE_PASS, /* type */ | |
366 | "evrp", /* name */ | |
367 | OPTGROUP_NONE, /* optinfo_flags */ | |
368 | TV_TREE_EARLY_VRP, /* tv_id */ | |
369 | PROP_ssa, /* properties_required */ | |
370 | 0, /* properties_provided */ | |
371 | 0, /* properties_destroyed */ | |
372 | 0, /* todo_flags_start */ | |
373 | ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ), | |
374 | }; | |
375 | ||
376 | class pass_early_vrp : public gimple_opt_pass | |
377 | { | |
378 | public: | |
379 | pass_early_vrp (gcc::context *ctxt) | |
380 | : gimple_opt_pass (pass_data_early_vrp, ctxt) | |
381 | {} | |
382 | ||
383 | /* opt_pass methods: */ | |
384 | opt_pass * clone () { return new pass_early_vrp (m_ctxt); } | |
385 | virtual bool gate (function *) | |
386 | { | |
387 | return flag_tree_vrp != 0; | |
388 | } | |
389 | virtual unsigned int execute (function *) | |
390 | { return execute_early_vrp (); } | |
391 | ||
392 | }; // class pass_vrp | |
393 | } // anon namespace | |
394 | ||
395 | gimple_opt_pass * | |
396 | make_pass_early_vrp (gcc::context *ctxt) | |
397 | { | |
398 | return new pass_early_vrp (ctxt); | |
399 | } |