]>
Commit | Line | Data |
---|---|---|
16207ddd | 1 | /* Support routines for Value Range Propagation (VRP). |
8d9254fc | 2 | Copyright (C) 2005-2020 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"); | |
63 | m_range_analyzer.dump_all_value_ranges (dump_file); | |
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 | { | |
242 | tree evrp_ret = evrp_folder::value_on_edge (e, op); | |
243 | tree ranger_ret = m_ranger->value_on_edge (e, op); | |
244 | return choose_value (evrp_ret, ranger_ret); | |
245 | } | |
246 | ||
247 | tree | |
248 | hybrid_folder::value_of_stmt (gimple *stmt, tree op) | |
249 | { | |
250 | tree evrp_ret = evrp_folder::value_of_stmt (stmt, op); | |
251 | tree ranger_ret = m_ranger->value_of_stmt (stmt, op); | |
252 | return choose_value (evrp_ret, ranger_ret); | |
253 | } | |
254 | ||
255 | // Given trees returned by EVRP and Ranger, choose/report the value to use | |
256 | // by the folder. | |
257 | ||
258 | tree | |
259 | hybrid_folder::choose_value (tree evrp_val, tree ranger_val) | |
260 | { | |
214d514f AH |
261 | // If both found the same value, just return it. |
262 | if (evrp_val && ranger_val && !compare_values (evrp_val, ranger_val)) | |
263 | return evrp_val; | |
264 | ||
265 | // If neither returned a value, return NULL_TREE. | |
266 | if (!ranger_val && !evrp_val) | |
267 | return NULL_TREE; | |
fcae5121 | 268 | |
214d514f AH |
269 | // Otherwise there is a discrepancy to flag. |
270 | if (dump_file) | |
271 | { | |
272 | if (evrp_val && ranger_val) | |
273 | fprintf (dump_file, "EVRP:hybrid: Disagreement\n"); | |
274 | if (evrp_val) | |
fcae5121 AM |
275 | { |
276 | fprintf (dump_file, "EVRP:hybrid: EVRP found singleton "); | |
277 | print_generic_expr (dump_file, evrp_val); | |
278 | fprintf (dump_file, "\n"); | |
279 | } | |
214d514f AH |
280 | if (ranger_val) |
281 | { | |
282 | fprintf (dump_file, "EVRP:hybrid: RVRP found singleton "); | |
283 | print_generic_expr (dump_file, ranger_val); | |
284 | fprintf (dump_file, "\n"); | |
285 | } | |
fcae5121 AM |
286 | } |
287 | ||
214d514f AH |
288 | // If one value was found, return it. |
289 | if (!evrp_val) | |
290 | return ranger_val; | |
291 | if (!ranger_val) | |
fcae5121 AM |
292 | return evrp_val; |
293 | ||
214d514f AH |
294 | // If values are different, return the first calculated value. |
295 | if ((param_evrp_mode & EVRP_MODE_RVRP_FIRST) == EVRP_MODE_RVRP_FIRST) | |
296 | return ranger_val; | |
297 | return evrp_val; | |
fcae5121 AM |
298 | } |
299 | ||
271eeb18 JL |
300 | /* Main entry point for the early vrp pass which is a simplified non-iterative |
301 | version of vrp where basic blocks are visited in dominance order. Value | |
302 | ranges discovered in early vrp will also be used by ipa-vrp. */ | |
303 | ||
304 | static unsigned int | |
305 | execute_early_vrp () | |
306 | { | |
1396fa5b AH |
307 | /* Ideally this setup code would move into the ctor for the folder |
308 | However, this setup can change the number of blocks which | |
271eeb18 | 309 | invalidates the internal arrays that are set up by the dominator |
1396fa5b | 310 | walker in substitute_and_fold_engine. */ |
271eeb18 JL |
311 | loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS); |
312 | rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); | |
313 | scev_initialize (); | |
314 | calculate_dominance_info (CDI_DOMINATORS); | |
271eeb18 | 315 | |
1e247c60 AH |
316 | // Only the last 2 bits matter for choosing the folder. |
317 | switch (param_evrp_mode & EVRP_MODE_RVRP_FIRST) | |
fcae5121 AM |
318 | { |
319 | case EVRP_MODE_EVRP_ONLY: | |
320 | { | |
321 | evrp_folder folder; | |
322 | folder.substitute_and_fold (); | |
323 | break; | |
324 | } | |
325 | case EVRP_MODE_RVRP_ONLY: | |
326 | { | |
327 | rvrp_folder folder; | |
328 | folder.substitute_and_fold (); | |
329 | break; | |
330 | } | |
331 | case EVRP_MODE_EVRP_FIRST: | |
332 | { | |
333 | hybrid_folder folder (true); | |
334 | folder.substitute_and_fold (); | |
335 | break; | |
336 | } | |
337 | case EVRP_MODE_RVRP_FIRST: | |
338 | { | |
339 | hybrid_folder folder (false); | |
340 | folder.substitute_and_fold (); | |
341 | break; | |
342 | } | |
343 | default: | |
344 | gcc_unreachable (); | |
345 | } | |
16207ddd JL |
346 | |
347 | scev_finalize (); | |
348 | loop_optimizer_finalize (); | |
349 | return 0; | |
350 | } | |
351 | ||
352 | namespace { | |
353 | ||
354 | const pass_data pass_data_early_vrp = | |
355 | { | |
356 | GIMPLE_PASS, /* type */ | |
357 | "evrp", /* name */ | |
358 | OPTGROUP_NONE, /* optinfo_flags */ | |
359 | TV_TREE_EARLY_VRP, /* tv_id */ | |
360 | PROP_ssa, /* properties_required */ | |
361 | 0, /* properties_provided */ | |
362 | 0, /* properties_destroyed */ | |
363 | 0, /* todo_flags_start */ | |
364 | ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ), | |
365 | }; | |
366 | ||
367 | class pass_early_vrp : public gimple_opt_pass | |
368 | { | |
369 | public: | |
370 | pass_early_vrp (gcc::context *ctxt) | |
371 | : gimple_opt_pass (pass_data_early_vrp, ctxt) | |
372 | {} | |
373 | ||
374 | /* opt_pass methods: */ | |
375 | opt_pass * clone () { return new pass_early_vrp (m_ctxt); } | |
376 | virtual bool gate (function *) | |
377 | { | |
378 | return flag_tree_vrp != 0; | |
379 | } | |
380 | virtual unsigned int execute (function *) | |
381 | { return execute_early_vrp (); } | |
382 | ||
383 | }; // class pass_vrp | |
384 | } // anon namespace | |
385 | ||
386 | gimple_opt_pass * | |
387 | make_pass_early_vrp (gcc::context *ctxt) | |
388 | { | |
389 | return new pass_early_vrp (ctxt); | |
390 | } |