Mercurial > hg > CbC > CbC_gcc

comparison gcc/gimple-ssa-evrp.c @ 131:84e7813d76e9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc-8.2
author mir3636
date Thu, 25 Oct 2018 07:37:49 +0900
parents
children 1830386684a0
comparison
equal deleted inserted replaced
111:04ced10e8804 131:84e7813d76e9
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