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