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