1/* Backward propagation of indirect loads through PHIs.
2   Copyright (C) 2007-2015 Free Software Foundation, Inc.
3   Contributed by Richard Guenther <rguenther@suse.de>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3.  If not see
19<http://www.gnu.org/licenses/>.  */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "tm.h"
25#include "hash-set.h"
26#include "machmode.h"
27#include "vec.h"
28#include "double-int.h"
29#include "input.h"
30#include "alias.h"
31#include "symtab.h"
32#include "wide-int.h"
33#include "inchash.h"
34#include "tree.h"
35#include "fold-const.h"
36#include "tm_p.h"
37#include "predict.h"
38#include "hard-reg-set.h"
39#include "input.h"
40#include "function.h"
41#include "dominance.h"
42#include "cfg.h"
43#include "basic-block.h"
44#include "gimple-pretty-print.h"
45#include "tree-ssa-alias.h"
46#include "internal-fn.h"
47#include "tree-eh.h"
48#include "gimple-expr.h"
49#include "is-a.h"
50#include "gimple.h"
51#include "gimplify.h"
52#include "gimple-iterator.h"
53#include "gimple-ssa.h"
54#include "tree-phinodes.h"
55#include "ssa-iterators.h"
56#include "stringpool.h"
57#include "tree-ssanames.h"
58#include "tree-pass.h"
59#include "langhooks.h"
60#include "flags.h"
61
62/* This pass propagates indirect loads through the PHI node for its
63   address to make the load source possibly non-addressable and to
64   allow for PHI optimization to trigger.
65
66   For example the pass changes
67
68     # addr_1 = PHI <&a, &b>
69     tmp_1 = *addr_1;
70
71   to
72
73     # tmp_1 = PHI <a, b>
74
75   but also handles more complex scenarios like
76
77     D.2077_2 = &this_1(D)->a1;
78     ...
79
80     # b_12 = PHI <&c(2), D.2077_2(3)>
81     D.2114_13 = *b_12;
82     ...
83
84     # b_15 = PHI <b_12(4), &b(5)>
85     D.2080_5 = &this_1(D)->a0;
86     ...
87
88     # b_18 = PHI <D.2080_5(6), &c(7)>
89     ...
90
91     # b_21 = PHI <b_15(8), b_18(9)>
92     D.2076_8 = *b_21;
93
94   where the addresses loaded are defined by PHIs itself.
95   The above happens for
96
97     std::max(std::min(a0, c), std::min(std::max(a1, c), b))
98
99   where this pass transforms it to a form later PHI optimization
100   recognizes and transforms it to the simple
101
102     D.2109_10 = this_1(D)->a1;
103     D.2110_11 = c;
104     D.2114_31 = MAX_EXPR <D.2109_10, D.2110_11>;
105     D.2115_14 = b;
106     D.2125_17 = MIN_EXPR <D.2115_14, D.2114_31>;
107     D.2119_16 = this_1(D)->a0;
108     D.2124_32 = MIN_EXPR <D.2110_11, D.2119_16>;
109     D.2076_33 = MAX_EXPR <D.2125_17, D.2124_32>;
110
111   The pass does a dominator walk processing loads using a basic-block
112   local analysis and stores the result for use by transformations on
113   dominated basic-blocks.  */
114
115
116/* Structure to keep track of the value of a dereferenced PHI result
117   and the virtual operand used for that dereference.  */
118
119struct phiprop_d
120{
121  tree value;
122  tree vuse;
123};
124
125/* Verify if the value recorded for NAME in PHIVN is still valid at
126   the start of basic block BB.  */
127
128static bool
129phivn_valid_p (struct phiprop_d *phivn, tree name, basic_block bb)
130{
131  tree vuse = phivn[SSA_NAME_VERSION (name)].vuse;
132  gimple use_stmt;
133  imm_use_iterator ui2;
134  bool ok = true;
135
136  /* The def stmts of the virtual uses need to be dominated by bb.  */
137  gcc_assert (vuse != NULL_TREE);
138
139  FOR_EACH_IMM_USE_STMT (use_stmt, ui2, vuse)
140    {
141      /* If BB does not dominate a VDEF, the value is invalid.  */
142      if ((gimple_vdef (use_stmt) != NULL_TREE
143	   || gimple_code (use_stmt) == GIMPLE_PHI)
144	  && !dominated_by_p (CDI_DOMINATORS, gimple_bb (use_stmt), bb))
145	{
146	  ok = false;
147	  BREAK_FROM_IMM_USE_STMT (ui2);
148	}
149    }
150
151  return ok;
152}
153
154/* Insert a new phi node for the dereference of PHI at basic_block
155   BB with the virtual operands from USE_STMT.  */
156
157static tree
158phiprop_insert_phi (basic_block bb, gphi *phi, gimple use_stmt,
159		    struct phiprop_d *phivn, size_t n)
160{
161  tree res;
162  gphi *new_phi;
163  edge_iterator ei;
164  edge e;
165
166  gcc_assert (is_gimple_assign (use_stmt)
167	      && gimple_assign_rhs_code (use_stmt) == MEM_REF);
168
169  /* Build a new PHI node to replace the definition of
170     the indirect reference lhs.  */
171  res = gimple_assign_lhs (use_stmt);
172  new_phi = create_phi_node (res, bb);
173
174  if (dump_file && (dump_flags & TDF_DETAILS))
175    {
176      fprintf (dump_file, "Inserting PHI for result of load ");
177      print_gimple_stmt (dump_file, use_stmt, 0, 0);
178    }
179
180  /* Add PHI arguments for each edge inserting loads of the
181     addressable operands.  */
182  FOR_EACH_EDGE (e, ei, bb->preds)
183    {
184      tree old_arg, new_var;
185      gassign *tmp;
186      source_location locus;
187
188      old_arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
189      locus = gimple_phi_arg_location_from_edge (phi, e);
190      while (TREE_CODE (old_arg) == SSA_NAME
191	     && (SSA_NAME_VERSION (old_arg) >= n
192	         || phivn[SSA_NAME_VERSION (old_arg)].value == NULL_TREE))
193	{
194	  gimple def_stmt = SSA_NAME_DEF_STMT (old_arg);
195	  old_arg = gimple_assign_rhs1 (def_stmt);
196	  locus = gimple_location (def_stmt);
197	}
198
199      if (TREE_CODE (old_arg) == SSA_NAME)
200	{
201	  if (dump_file && (dump_flags & TDF_DETAILS))
202	    {
203	      fprintf (dump_file, "  for edge defining ");
204	      print_generic_expr (dump_file, PHI_ARG_DEF_FROM_EDGE (phi, e), 0);
205	      fprintf (dump_file, " reusing PHI result ");
206	      print_generic_expr (dump_file,
207				  phivn[SSA_NAME_VERSION (old_arg)].value, 0);
208	      fprintf (dump_file, "\n");
209	    }
210	  /* Reuse a formerly created dereference.  */
211	  new_var = phivn[SSA_NAME_VERSION (old_arg)].value;
212	}
213      else
214	{
215	  tree rhs = gimple_assign_rhs1 (use_stmt);
216	  gcc_assert (TREE_CODE (old_arg) == ADDR_EXPR);
217	  new_var = make_ssa_name (TREE_TYPE (rhs));
218	  if (!is_gimple_min_invariant (old_arg))
219	    old_arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
220	  else
221	    old_arg = unshare_expr (old_arg);
222	  tmp = gimple_build_assign (new_var,
223				     fold_build2 (MEM_REF, TREE_TYPE (rhs),
224						  old_arg,
225						  TREE_OPERAND (rhs, 1)));
226	  gimple_set_location (tmp, locus);
227
228	  gsi_insert_on_edge (e, tmp);
229	  update_stmt (tmp);
230
231	  if (dump_file && (dump_flags & TDF_DETAILS))
232	    {
233	      fprintf (dump_file, "  for edge defining ");
234	      print_generic_expr (dump_file, PHI_ARG_DEF_FROM_EDGE (phi, e), 0);
235	      fprintf (dump_file, " inserting load ");
236	      print_gimple_stmt (dump_file, tmp, 0, 0);
237	    }
238	}
239
240      add_phi_arg (new_phi, new_var, e, locus);
241    }
242
243  update_stmt (new_phi);
244
245  if (dump_file && (dump_flags & TDF_DETAILS))
246    print_gimple_stmt (dump_file, new_phi, 0, 0);
247
248  return res;
249}
250
251/* Propagate between the phi node arguments of PHI in BB and phi result
252   users.  For now this matches
253        # p_2 = PHI <&x, &y>
254      <Lx>:;
255	p_3 = p_2;
256	z_2 = *p_3;
257   and converts it to
258	# z_2 = PHI <x, y>
259      <Lx>:;
260   Returns true if a transformation was done and edge insertions
261   need to be committed.  Global data PHIVN and N is used to track
262   past transformation results.  We need to be especially careful here
263   with aliasing issues as we are moving memory reads.  */
264
265static bool
266propagate_with_phi (basic_block bb, gphi *phi, struct phiprop_d *phivn,
267		    size_t n)
268{
269  tree ptr = PHI_RESULT (phi);
270  gimple use_stmt;
271  tree res = NULL_TREE;
272  gimple_stmt_iterator gsi;
273  imm_use_iterator ui;
274  use_operand_p arg_p, use;
275  ssa_op_iter i;
276  bool phi_inserted;
277  tree type = NULL_TREE;
278
279  if (!POINTER_TYPE_P (TREE_TYPE (ptr))
280      || !is_gimple_reg_type (TREE_TYPE (TREE_TYPE (ptr))))
281    return false;
282
283  /* Check if we can "cheaply" dereference all phi arguments.  */
284  FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
285    {
286      tree arg = USE_FROM_PTR (arg_p);
287      /* Walk the ssa chain until we reach a ssa name we already
288	 created a value for or we reach a definition of the form
289	 ssa_name_n = &var;  */
290      while (TREE_CODE (arg) == SSA_NAME
291	     && !SSA_NAME_IS_DEFAULT_DEF (arg)
292	     && (SSA_NAME_VERSION (arg) >= n
293	         || phivn[SSA_NAME_VERSION (arg)].value == NULL_TREE))
294	{
295	  gimple def_stmt = SSA_NAME_DEF_STMT (arg);
296	  if (!gimple_assign_single_p (def_stmt))
297	    return false;
298	  arg = gimple_assign_rhs1 (def_stmt);
299	}
300      if (TREE_CODE (arg) != ADDR_EXPR
301	  && !(TREE_CODE (arg) == SSA_NAME
302	       && SSA_NAME_VERSION (arg) < n
303	       && phivn[SSA_NAME_VERSION (arg)].value != NULL_TREE
304	       && (!type
305		   || types_compatible_p
306		       (type, TREE_TYPE (phivn[SSA_NAME_VERSION (arg)].value)))
307	       && phivn_valid_p (phivn, arg, bb)))
308	return false;
309      if (!type
310	  && TREE_CODE (arg) == SSA_NAME)
311	type = TREE_TYPE (phivn[SSA_NAME_VERSION (arg)].value);
312    }
313
314  /* Find a dereferencing use.  First follow (single use) ssa
315     copy chains for ptr.  */
316  while (single_imm_use (ptr, &use, &use_stmt)
317	 && gimple_assign_ssa_name_copy_p (use_stmt))
318    ptr = gimple_assign_lhs (use_stmt);
319
320  /* Replace the first dereference of *ptr if there is one and if we
321     can move the loads to the place of the ptr phi node.  */
322  phi_inserted = false;
323  FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr)
324    {
325      gimple def_stmt;
326      tree vuse;
327
328      /* Only replace loads in blocks that post-dominate the PHI node.  That
329         makes sure we don't end up speculating loads.  */
330      if (!dominated_by_p (CDI_POST_DOMINATORS,
331			   bb, gimple_bb (use_stmt)))
332	continue;
333
334      /* Check whether this is a load of *ptr.  */
335      if (!(is_gimple_assign (use_stmt)
336	    && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
337	    && gimple_assign_rhs_code (use_stmt) == MEM_REF
338	    && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == ptr
339	    && integer_zerop (TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 1))
340	    && (!type
341		|| types_compatible_p
342		     (TREE_TYPE (gimple_assign_lhs (use_stmt)), type))
343	    /* We cannot replace a load that may throw or is volatile.  */
344	    && !stmt_can_throw_internal (use_stmt)))
345	continue;
346
347      /* Check if we can move the loads.  The def stmt of the virtual use
348	 needs to be in a different basic block dominating bb.  */
349      vuse = gimple_vuse (use_stmt);
350      def_stmt = SSA_NAME_DEF_STMT (vuse);
351      if (!SSA_NAME_IS_DEFAULT_DEF (vuse)
352	  && (gimple_bb (def_stmt) == bb
353	      || !dominated_by_p (CDI_DOMINATORS,
354				  bb, gimple_bb (def_stmt))))
355	goto next;
356
357      /* Found a proper dereference.  Insert a phi node if this
358	 is the first load transformation.  */
359      if (!phi_inserted)
360	{
361	  res = phiprop_insert_phi (bb, phi, use_stmt, phivn, n);
362	  type = TREE_TYPE (res);
363
364	  /* Remember the value we created for *ptr.  */
365	  phivn[SSA_NAME_VERSION (ptr)].value = res;
366	  phivn[SSA_NAME_VERSION (ptr)].vuse = vuse;
367
368	  /* Remove old stmt.  The phi is taken care of by DCE, if we
369	     want to delete it here we also have to delete all intermediate
370	     copies.  */
371	  gsi = gsi_for_stmt (use_stmt);
372	  gsi_remove (&gsi, true);
373
374	  phi_inserted = true;
375	}
376      else
377	{
378	  /* Further replacements are easy, just make a copy out of the
379	     load.  */
380	  gimple_assign_set_rhs1 (use_stmt, res);
381	  update_stmt (use_stmt);
382	}
383
384next:;
385      /* Continue searching for a proper dereference.  */
386    }
387
388  return phi_inserted;
389}
390
391/* Main entry for phiprop pass.  */
392
393namespace {
394
395const pass_data pass_data_phiprop =
396{
397  GIMPLE_PASS, /* type */
398  "phiprop", /* name */
399  OPTGROUP_NONE, /* optinfo_flags */
400  TV_TREE_PHIPROP, /* tv_id */
401  ( PROP_cfg | PROP_ssa ), /* properties_required */
402  0, /* properties_provided */
403  0, /* properties_destroyed */
404  0, /* todo_flags_start */
405  TODO_update_ssa, /* todo_flags_finish */
406};
407
408class pass_phiprop : public gimple_opt_pass
409{
410public:
411  pass_phiprop (gcc::context *ctxt)
412    : gimple_opt_pass (pass_data_phiprop, ctxt)
413  {}
414
415  /* opt_pass methods: */
416  virtual bool gate (function *) { return flag_tree_phiprop; }
417  virtual unsigned int execute (function *);
418
419}; // class pass_phiprop
420
421unsigned int
422pass_phiprop::execute (function *fun)
423{
424  vec<basic_block> bbs;
425  struct phiprop_d *phivn;
426  bool did_something = false;
427  basic_block bb;
428  gphi_iterator gsi;
429  unsigned i;
430  size_t n;
431
432  calculate_dominance_info (CDI_DOMINATORS);
433  calculate_dominance_info (CDI_POST_DOMINATORS);
434
435  n = num_ssa_names;
436  phivn = XCNEWVEC (struct phiprop_d, n);
437
438  /* Walk the dominator tree in preorder.  */
439  bbs = get_all_dominated_blocks (CDI_DOMINATORS,
440				  single_succ (ENTRY_BLOCK_PTR_FOR_FN (fun)));
441  FOR_EACH_VEC_ELT (bbs, i, bb)
442    for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
443      did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n);
444
445  if (did_something)
446    gsi_commit_edge_inserts ();
447
448  bbs.release ();
449  free (phivn);
450
451  free_dominance_info (CDI_POST_DOMINATORS);
452
453  return 0;
454}
455
456} // anon namespace
457
458gimple_opt_pass *
459make_pass_phiprop (gcc::context *ctxt)
460{
461  return new pass_phiprop (ctxt);
462}
463