|
131
|
1 /* Support routines for Value Range Propagation (VRP).
|
|
145
|
2 Copyright (C) 2005-2020 Free Software Foundation, Inc.
|
|
131
|
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"
|
|
|
43 #include "gimple-ssa-evrp-analyze.h"
|
|
|
44
|
|
|
45 class evrp_folder : public substitute_and_fold_engine
|
|
|
46 {
|
|
|
47 public:
|
|
|
48 tree get_value (tree) FINAL OVERRIDE;
|
|
|
49 evrp_folder (class vr_values *vr_values_) : vr_values (vr_values_) { }
|
|
|
50 bool simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
|
|
|
51 { return vr_values->simplify_stmt_using_ranges (gsi); }
|
|
|
52 class vr_values *vr_values;
|
|
|
53
|
|
|
54 private:
|
|
|
55 DISABLE_COPY_AND_ASSIGN (evrp_folder);
|
|
|
56 };
|
|
|
57
|
|
|
58 tree
|
|
|
59 evrp_folder::get_value (tree op)
|
|
|
60 {
|
|
|
61 return vr_values->op_with_constant_singleton_value_range (op);
|
|
|
62 }
|
|
|
63
|
|
|
64 /* evrp_dom_walker visits the basic blocks in the dominance order and set
|
|
|
65 the Value Ranges (VR) for SSA_NAMEs in the scope. Use this VR to
|
|
|
66 discover more VRs. */
|
|
|
67
|
|
|
68 class evrp_dom_walker : public dom_walker
|
|
|
69 {
|
|
|
70 public:
|
|
|
71 evrp_dom_walker ()
|
|
|
72 : dom_walker (CDI_DOMINATORS),
|
|
145
|
73 evrp_range_analyzer (true),
|
|
131
|
74 evrp_folder (evrp_range_analyzer.get_vr_values ())
|
|
|
75 {
|
|
|
76 need_eh_cleanup = BITMAP_ALLOC (NULL);
|
|
|
77 }
|
|
|
78 ~evrp_dom_walker ()
|
|
|
79 {
|
|
|
80 BITMAP_FREE (need_eh_cleanup);
|
|
|
81 }
|
|
|
82 virtual edge before_dom_children (basic_block);
|
|
|
83 virtual void after_dom_children (basic_block);
|
|
|
84 void cleanup (void);
|
|
|
85
|
|
|
86 private:
|
|
|
87 DISABLE_COPY_AND_ASSIGN (evrp_dom_walker);
|
|
|
88 bitmap need_eh_cleanup;
|
|
|
89 auto_vec<gimple *> stmts_to_fixup;
|
|
|
90 auto_vec<gimple *> stmts_to_remove;
|
|
|
91
|
|
|
92 class evrp_range_analyzer evrp_range_analyzer;
|
|
|
93 class evrp_folder evrp_folder;
|
|
|
94 };
|
|
|
95
|
|
|
96 edge
|
|
|
97 evrp_dom_walker::before_dom_children (basic_block bb)
|
|
|
98 {
|
|
|
99 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
100 fprintf (dump_file, "Visiting BB%d\n", bb->index);
|
|
|
101
|
|
|
102 evrp_range_analyzer.enter (bb);
|
|
|
103
|
|
|
104 for (gphi_iterator gpi = gsi_start_phis (bb);
|
|
|
105 !gsi_end_p (gpi); gsi_next (&gpi))
|
|
|
106 {
|
|
|
107 gphi *phi = gpi.phi ();
|
|
|
108 tree lhs = PHI_RESULT (phi);
|
|
|
109 if (virtual_operand_p (lhs))
|
|
|
110 continue;
|
|
|
111
|
|
145
|
112 const value_range_equiv *vr = evrp_range_analyzer.get_value_range (lhs);
|
|
131
|
113 /* Mark PHIs whose lhs we fully propagate for removal. */
|
|
145
|
114 tree val;
|
|
|
115 if (vr->singleton_p (&val) && may_propagate_copy (lhs, val))
|
|
131
|
116 {
|
|
|
117 stmts_to_remove.safe_push (phi);
|
|
|
118 continue;
|
|
|
119 }
|
|
|
120 }
|
|
|
121
|
|
|
122 edge taken_edge = NULL;
|
|
|
123
|
|
|
124 /* Visit all other stmts and discover any new VRs possible. */
|
|
|
125 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
|
|
|
126 !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
127 {
|
|
|
128 gimple *stmt = gsi_stmt (gsi);
|
|
|
129 tree output = NULL_TREE;
|
|
|
130 gimple *old_stmt = stmt;
|
|
|
131 bool was_noreturn = (is_gimple_call (stmt)
|
|
|
132 && gimple_call_noreturn_p (stmt));
|
|
|
133
|
|
|
134 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
135 {
|
|
|
136 fprintf (dump_file, "Visiting stmt ");
|
|
|
137 print_gimple_stmt (dump_file, stmt, 0);
|
|
|
138 }
|
|
|
139
|
|
|
140 evrp_range_analyzer.record_ranges_from_stmt (stmt, false);
|
|
|
141
|
|
|
142 if (gcond *cond = dyn_cast <gcond *> (stmt))
|
|
|
143 {
|
|
|
144 evrp_range_analyzer.vrp_visit_cond_stmt (cond, &taken_edge);
|
|
|
145 if (taken_edge)
|
|
|
146 {
|
|
|
147 if (taken_edge->flags & EDGE_TRUE_VALUE)
|
|
|
148 gimple_cond_make_true (cond);
|
|
|
149 else if (taken_edge->flags & EDGE_FALSE_VALUE)
|
|
|
150 gimple_cond_make_false (cond);
|
|
|
151 else
|
|
|
152 gcc_unreachable ();
|
|
|
153 update_stmt (stmt);
|
|
|
154 }
|
|
|
155 }
|
|
|
156 else if (stmt_interesting_for_vrp (stmt))
|
|
|
157 {
|
|
|
158 output = get_output_for_vrp (stmt);
|
|
|
159 if (output)
|
|
|
160 {
|
|
145
|
161 const value_range_equiv *vr
|
|
|
162 = evrp_range_analyzer.get_value_range (output);
|
|
131
|
163
|
|
|
164 /* Mark stmts whose output we fully propagate for removal. */
|
|
145
|
165 tree val;
|
|
|
166 if (vr->singleton_p (&val)
|
|
131
|
167 && may_propagate_copy (output, val)
|
|
|
168 && !stmt_could_throw_p (cfun, stmt)
|
|
|
169 && !gimple_has_side_effects (stmt))
|
|
|
170 {
|
|
|
171 stmts_to_remove.safe_push (stmt);
|
|
|
172 continue;
|
|
|
173 }
|
|
|
174 }
|
|
|
175 }
|
|
|
176
|
|
|
177 /* Try folding stmts with the VR discovered. */
|
|
|
178 bool did_replace = evrp_folder.replace_uses_in (stmt);
|
|
145
|
179 gimple_stmt_iterator prev_gsi = gsi;
|
|
|
180 gsi_prev (&prev_gsi);
|
|
131
|
181 if (fold_stmt (&gsi, follow_single_use_edges)
|
|
|
182 || did_replace)
|
|
|
183 {
|
|
|
184 stmt = gsi_stmt (gsi);
|
|
|
185 update_stmt (stmt);
|
|
|
186 did_replace = true;
|
|
|
187 }
|
|
|
188 if (evrp_folder.simplify_stmt_using_ranges (&gsi))
|
|
|
189 {
|
|
|
190 stmt = gsi_stmt (gsi);
|
|
|
191 update_stmt (stmt);
|
|
|
192 did_replace = true;
|
|
|
193 }
|
|
|
194
|
|
|
195 if (did_replace)
|
|
|
196 {
|
|
145
|
197 /* If we wound up generating new stmts during folding
|
|
|
198 drop all their defs to VARYING. We can't easily
|
|
|
199 process them because we've already instantiated
|
|
|
200 ranges on uses on STMT that only hold after it. */
|
|
|
201 if (gsi_end_p (prev_gsi))
|
|
|
202 prev_gsi = gsi_start_bb (bb);
|
|
|
203 else
|
|
|
204 gsi_next (&prev_gsi);
|
|
|
205 while (gsi_stmt (prev_gsi) != gsi_stmt (gsi))
|
|
|
206 {
|
|
|
207 evrp_range_analyzer.get_vr_values ()
|
|
|
208 ->set_defs_to_varying (gsi_stmt (prev_gsi));
|
|
|
209 gsi_next (&prev_gsi);
|
|
|
210 }
|
|
|
211
|
|
131
|
212 /* If we cleaned up EH information from the statement,
|
|
|
213 remove EH edges. */
|
|
|
214 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
|
|
|
215 bitmap_set_bit (need_eh_cleanup, bb->index);
|
|
|
216
|
|
|
217 /* If we turned a not noreturn call into a noreturn one
|
|
|
218 schedule it for fixup. */
|
|
|
219 if (!was_noreturn
|
|
|
220 && is_gimple_call (stmt)
|
|
|
221 && gimple_call_noreturn_p (stmt))
|
|
|
222 stmts_to_fixup.safe_push (stmt);
|
|
|
223
|
|
|
224 if (gimple_assign_single_p (stmt))
|
|
|
225 {
|
|
|
226 tree rhs = gimple_assign_rhs1 (stmt);
|
|
|
227 if (TREE_CODE (rhs) == ADDR_EXPR)
|
|
|
228 recompute_tree_invariant_for_addr_expr (rhs);
|
|
|
229 }
|
|
|
230 }
|
|
|
231 }
|
|
|
232
|
|
|
233 /* Visit BB successor PHI nodes and replace PHI args. */
|
|
|
234 edge e;
|
|
|
235 edge_iterator ei;
|
|
|
236 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
|
237 {
|
|
|
238 for (gphi_iterator gpi = gsi_start_phis (e->dest);
|
|
|
239 !gsi_end_p (gpi); gsi_next (&gpi))
|
|
|
240 {
|
|
|
241 gphi *phi = gpi.phi ();
|
|
|
242 use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
|
|
|
243 tree arg = USE_FROM_PTR (use_p);
|
|
|
244 if (TREE_CODE (arg) != SSA_NAME
|
|
|
245 || virtual_operand_p (arg))
|
|
|
246 continue;
|
|
145
|
247 const value_range_equiv
|
|
|
248 *vr = evrp_range_analyzer.get_value_range (arg);
|
|
|
249 tree val;
|
|
|
250 if (vr->singleton_p (&val) && may_propagate_copy (arg, val))
|
|
131
|
251 propagate_value (use_p, val);
|
|
|
252 }
|
|
|
253 }
|
|
|
254
|
|
|
255 return taken_edge;
|
|
|
256 }
|
|
|
257
|
|
|
258 void
|
|
|
259 evrp_dom_walker::after_dom_children (basic_block bb)
|
|
|
260 {
|
|
|
261 evrp_range_analyzer.leave (bb);
|
|
|
262 }
|
|
|
263
|
|
|
264 /* Perform any cleanups after the main phase of EVRP has completed. */
|
|
|
265
|
|
|
266 void
|
|
|
267 evrp_dom_walker::cleanup (void)
|
|
|
268 {
|
|
|
269 if (dump_file)
|
|
|
270 {
|
|
|
271 fprintf (dump_file, "\nValue ranges after Early VRP:\n\n");
|
|
|
272 evrp_range_analyzer.dump_all_value_ranges (dump_file);
|
|
|
273 fprintf (dump_file, "\n");
|
|
|
274 }
|
|
|
275
|
|
|
276 /* Remove stmts in reverse order to make debug stmt creation possible. */
|
|
|
277 while (! stmts_to_remove.is_empty ())
|
|
|
278 {
|
|
|
279 gimple *stmt = stmts_to_remove.pop ();
|
|
|
280 if (dump_file && dump_flags & TDF_DETAILS)
|
|
|
281 {
|
|
|
282 fprintf (dump_file, "Removing dead stmt ");
|
|
|
283 print_gimple_stmt (dump_file, stmt, 0);
|
|
|
284 fprintf (dump_file, "\n");
|
|
|
285 }
|
|
|
286 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
|
|
|
287 if (gimple_code (stmt) == GIMPLE_PHI)
|
|
|
288 remove_phi_node (&gsi, true);
|
|
|
289 else
|
|
|
290 {
|
|
|
291 unlink_stmt_vdef (stmt);
|
|
|
292 gsi_remove (&gsi, true);
|
|
|
293 release_defs (stmt);
|
|
|
294 }
|
|
|
295 }
|
|
|
296
|
|
|
297 if (!bitmap_empty_p (need_eh_cleanup))
|
|
|
298 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
|
|
|
299
|
|
|
300 /* Fixup stmts that became noreturn calls. This may require splitting
|
|
|
301 blocks and thus isn't possible during the dominator walk. Do this
|
|
|
302 in reverse order so we don't inadvertedly remove a stmt we want to
|
|
|
303 fixup by visiting a dominating now noreturn call first. */
|
|
|
304 while (!stmts_to_fixup.is_empty ())
|
|
|
305 {
|
|
|
306 gimple *stmt = stmts_to_fixup.pop ();
|
|
|
307 fixup_noreturn_call (stmt);
|
|
|
308 }
|
|
|
309
|
|
|
310 evrp_folder.vr_values->cleanup_edges_and_switches ();
|
|
|
311 }
|
|
|
312
|
|
|
313 /* Main entry point for the early vrp pass which is a simplified non-iterative
|
|
|
314 version of vrp where basic blocks are visited in dominance order. Value
|
|
|
315 ranges discovered in early vrp will also be used by ipa-vrp. */
|
|
|
316
|
|
|
317 static unsigned int
|
|
|
318 execute_early_vrp ()
|
|
|
319 {
|
|
|
320 /* Ideally this setup code would move into the ctor for the dominator
|
|
|
321 walk. However, this setup can change the number of blocks which
|
|
|
322 invalidates the internal arrays that are set up by the dominator
|
|
|
323 walker. */
|
|
|
324 loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
|
|
|
325 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
|
|
|
326 scev_initialize ();
|
|
|
327 calculate_dominance_info (CDI_DOMINATORS);
|
|
|
328
|
|
|
329 /* Walk stmts in dominance order and propagate VRP. */
|
|
|
330 evrp_dom_walker walker;
|
|
|
331 walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
|
|
|
332 walker.cleanup ();
|
|
|
333
|
|
|
334 scev_finalize ();
|
|
|
335 loop_optimizer_finalize ();
|
|
|
336 return 0;
|
|
|
337 }
|
|
|
338
|
|
|
339 namespace {
|
|
|
340
|
|
|
341 const pass_data pass_data_early_vrp =
|
|
|
342 {
|
|
|
343 GIMPLE_PASS, /* type */
|
|
|
344 "evrp", /* name */
|
|
|
345 OPTGROUP_NONE, /* optinfo_flags */
|
|
|
346 TV_TREE_EARLY_VRP, /* tv_id */
|
|
|
347 PROP_ssa, /* properties_required */
|
|
|
348 0, /* properties_provided */
|
|
|
349 0, /* properties_destroyed */
|
|
|
350 0, /* todo_flags_start */
|
|
|
351 ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ),
|
|
|
352 };
|
|
|
353
|
|
|
354 class pass_early_vrp : public gimple_opt_pass
|
|
|
355 {
|
|
|
356 public:
|
|
|
357 pass_early_vrp (gcc::context *ctxt)
|
|
|
358 : gimple_opt_pass (pass_data_early_vrp, ctxt)
|
|
|
359 {}
|
|
|
360
|
|
|
361 /* opt_pass methods: */
|
|
|
362 opt_pass * clone () { return new pass_early_vrp (m_ctxt); }
|
|
|
363 virtual bool gate (function *)
|
|
|
364 {
|
|
|
365 return flag_tree_vrp != 0;
|
|
|
366 }
|
|
|
367 virtual unsigned int execute (function *)
|
|
|
368 { return execute_early_vrp (); }
|
|
|
369
|
|
|
370 }; // class pass_vrp
|
|
|
371 } // anon namespace
|
|
|
372
|
|
|
373 gimple_opt_pass *
|
|
|
374 make_pass_early_vrp (gcc::context *ctxt)
|
|
|
375 {
|
|
|
376 return new pass_early_vrp (ctxt);
|
|
|
377 }
|
|
|
378
|
