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