[19/46] Make vect_dr_stmt return a stmt_vec_info
[official-gcc.git] / gcc / gimple-ssa-evrp.c
blobb9a054fd2ee5c63cc66db44ba5a9b778ed38d36d
1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005-2018 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
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/>. */
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"
45 class evrp_folder : public substitute_and_fold_engine
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;
54 private:
55 DISABLE_COPY_AND_ASSIGN (evrp_folder);
58 tree
59 evrp_folder::get_value (tree op)
61 return vr_values->op_with_constant_singleton_value_range (op);
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. */
68 class evrp_dom_walker : public dom_walker
70 public:
71 evrp_dom_walker ()
72 : dom_walker (CDI_DOMINATORS),
73 evrp_folder (evrp_range_analyzer.get_vr_values ())
75 need_eh_cleanup = BITMAP_ALLOC (NULL);
77 ~evrp_dom_walker ()
79 BITMAP_FREE (need_eh_cleanup);
81 virtual edge before_dom_children (basic_block);
82 virtual void after_dom_children (basic_block);
83 void cleanup (void);
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;
91 class evrp_range_analyzer evrp_range_analyzer;
92 class evrp_folder evrp_folder;
95 edge
96 evrp_dom_walker::before_dom_children (basic_block bb)
98 if (dump_file && (dump_flags & TDF_DETAILS))
99 fprintf (dump_file, "Visiting BB%d\n", bb->index);
101 evrp_range_analyzer.enter (bb);
103 for (gphi_iterator gpi = gsi_start_phis (bb);
104 !gsi_end_p (gpi); gsi_next (&gpi))
106 gphi *phi = gpi.phi ();
107 tree lhs = PHI_RESULT (phi);
108 if (virtual_operand_p (lhs))
109 continue;
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))
116 stmts_to_remove.safe_push (phi);
117 continue;
121 edge taken_edge = NULL;
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))
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));
133 if (dump_file && (dump_flags & TDF_DETAILS))
135 fprintf (dump_file, "Visiting stmt ");
136 print_gimple_stmt (dump_file, stmt, 0);
139 evrp_range_analyzer.record_ranges_from_stmt (stmt, false);
141 if (gcond *cond = dyn_cast <gcond *> (stmt))
143 evrp_range_analyzer.vrp_visit_cond_stmt (cond, &taken_edge);
144 if (taken_edge)
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);
155 else if (stmt_interesting_for_vrp (stmt))
157 output = get_output_for_vrp (stmt);
158 if (output)
160 tree val;
161 value_range *vr = evrp_range_analyzer.get_value_range (output);
163 /* Mark stmts whose output we fully propagate for removal. */
164 if ((vr->type == VR_RANGE || vr->type == VR_ANTI_RANGE)
165 && (val = value_range_constant_singleton (vr))
166 && may_propagate_copy (output, val)
167 && !stmt_could_throw_p (stmt)
168 && !gimple_has_side_effects (stmt))
170 stmts_to_remove.safe_push (stmt);
171 continue;
176 /* Try folding stmts with the VR discovered. */
177 bool did_replace = evrp_folder.replace_uses_in (stmt);
178 if (fold_stmt (&gsi, follow_single_use_edges)
179 || did_replace)
181 stmt = gsi_stmt (gsi);
182 update_stmt (stmt);
183 did_replace = true;
185 if (evrp_folder.simplify_stmt_using_ranges (&gsi))
187 stmt = gsi_stmt (gsi);
188 update_stmt (stmt);
189 did_replace = true;
192 if (did_replace)
194 /* If we cleaned up EH information from the statement,
195 remove EH edges. */
196 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
197 bitmap_set_bit (need_eh_cleanup, bb->index);
199 /* If we turned a not noreturn call into a noreturn one
200 schedule it for fixup. */
201 if (!was_noreturn
202 && is_gimple_call (stmt)
203 && gimple_call_noreturn_p (stmt))
204 stmts_to_fixup.safe_push (stmt);
206 if (gimple_assign_single_p (stmt))
208 tree rhs = gimple_assign_rhs1 (stmt);
209 if (TREE_CODE (rhs) == ADDR_EXPR)
210 recompute_tree_invariant_for_addr_expr (rhs);
215 /* Visit BB successor PHI nodes and replace PHI args. */
216 edge e;
217 edge_iterator ei;
218 FOR_EACH_EDGE (e, ei, bb->succs)
220 for (gphi_iterator gpi = gsi_start_phis (e->dest);
221 !gsi_end_p (gpi); gsi_next (&gpi))
223 gphi *phi = gpi.phi ();
224 use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
225 tree arg = USE_FROM_PTR (use_p);
226 if (TREE_CODE (arg) != SSA_NAME
227 || virtual_operand_p (arg))
228 continue;
229 value_range *vr = evrp_range_analyzer.get_value_range (arg);
230 tree val = value_range_constant_singleton (vr);
231 if (val && may_propagate_copy (arg, val))
232 propagate_value (use_p, val);
236 return taken_edge;
239 void
240 evrp_dom_walker::after_dom_children (basic_block bb)
242 evrp_range_analyzer.leave (bb);
245 /* Perform any cleanups after the main phase of EVRP has completed. */
247 void
248 evrp_dom_walker::cleanup (void)
250 if (dump_file)
252 fprintf (dump_file, "\nValue ranges after Early VRP:\n\n");
253 evrp_range_analyzer.dump_all_value_ranges (dump_file);
254 fprintf (dump_file, "\n");
257 /* Remove stmts in reverse order to make debug stmt creation possible. */
258 while (! stmts_to_remove.is_empty ())
260 gimple *stmt = stmts_to_remove.pop ();
261 if (dump_file && dump_flags & TDF_DETAILS)
263 fprintf (dump_file, "Removing dead stmt ");
264 print_gimple_stmt (dump_file, stmt, 0);
265 fprintf (dump_file, "\n");
267 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
268 if (gimple_code (stmt) == GIMPLE_PHI)
269 remove_phi_node (&gsi, true);
270 else
272 unlink_stmt_vdef (stmt);
273 gsi_remove (&gsi, true);
274 release_defs (stmt);
278 if (!bitmap_empty_p (need_eh_cleanup))
279 gimple_purge_all_dead_eh_edges (need_eh_cleanup);
281 /* Fixup stmts that became noreturn calls. This may require splitting
282 blocks and thus isn't possible during the dominator walk. Do this
283 in reverse order so we don't inadvertedly remove a stmt we want to
284 fixup by visiting a dominating now noreturn call first. */
285 while (!stmts_to_fixup.is_empty ())
287 gimple *stmt = stmts_to_fixup.pop ();
288 fixup_noreturn_call (stmt);
292 /* Main entry point for the early vrp pass which is a simplified non-iterative
293 version of vrp where basic blocks are visited in dominance order. Value
294 ranges discovered in early vrp will also be used by ipa-vrp. */
296 static unsigned int
297 execute_early_vrp ()
299 /* Ideally this setup code would move into the ctor for the dominator
300 walk. However, this setup can change the number of blocks which
301 invalidates the internal arrays that are set up by the dominator
302 walker. */
303 loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
304 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
305 scev_initialize ();
306 calculate_dominance_info (CDI_DOMINATORS);
308 /* Walk stmts in dominance order and propagate VRP. */
309 evrp_dom_walker walker;
310 walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
311 walker.cleanup ();
313 scev_finalize ();
314 loop_optimizer_finalize ();
315 return 0;
318 namespace {
320 const pass_data pass_data_early_vrp =
322 GIMPLE_PASS, /* type */
323 "evrp", /* name */
324 OPTGROUP_NONE, /* optinfo_flags */
325 TV_TREE_EARLY_VRP, /* tv_id */
326 PROP_ssa, /* properties_required */
327 0, /* properties_provided */
328 0, /* properties_destroyed */
329 0, /* todo_flags_start */
330 ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ),
333 class pass_early_vrp : public gimple_opt_pass
335 public:
336 pass_early_vrp (gcc::context *ctxt)
337 : gimple_opt_pass (pass_data_early_vrp, ctxt)
340 /* opt_pass methods: */
341 opt_pass * clone () { return new pass_early_vrp (m_ctxt); }
342 virtual bool gate (function *)
344 return flag_tree_vrp != 0;
346 virtual unsigned int execute (function *)
347 { return execute_early_vrp (); }
349 }; // class pass_vrp
350 } // anon namespace
352 gimple_opt_pass *
353 make_pass_early_vrp (gcc::context *ctxt)
355 return new pass_early_vrp (ctxt);