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