OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [tree-ssa-phiprop.c] - Blame information for rev 859

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.