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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [ipa-cp.c] - Blame information for rev 841

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

Line No. Rev Author Line
1 38 julius
/* Interprocedural constant propagation
2
   Copyright (C) 2005, 2007 Free Software Foundation, Inc.
3
   Contributed by Razya Ladelsky <RAZYA@il.ibm.com>
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify it under
8
the terms of the GNU General Public License as published by the Free
9
Software Foundation; either version 3, or (at your option) any later
10
version.
11
 
12
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13
WARRANTY; without even the implied warranty of MERCHANTABILITY or
14
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15
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
/* Interprocedural constant propagation.
22
   The aim of interprocedural constant propagation (IPCP) is to find which
23
   function's argument has the same constant value in each invocation throughout
24
   the whole program. For example, for an application consisting of two files,
25
   foo1.c, foo2.c:
26
 
27
   foo1.c contains :
28
 
29
   int f (int x)
30
   {
31
     g (x);
32
   }
33
   void main (void)
34
   {
35
     f (3);
36
     h (3);
37
   }
38
 
39
   foo2.c contains :
40
 
41
   int h (int y)
42
   {
43
     g (y);
44
   }
45
   int g (int y)
46
   {
47
     printf ("value is %d",y);
48
   }
49
 
50
   The IPCP algorithm will find that g's formal argument y
51
   is always called with the value 3.
52
 
53
   The algorithm used is based on "Interprocedural Constant Propagation",
54
   by Challahan David, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86,
55
   pg 152-161
56
 
57
   The optimization is divided into three stages:
58
 
59
   First stage - intraprocedural analysis
60
   =======================================
61
   This phase computes jump_function and modify information.
62
 
63
   A jump function for a callsite represents the values passed as actual
64
   arguments
65
   of the callsite. There are three types of values :
66
   Formal - the caller's formal parameter is passed as an actual argument.
67
   Constant - a constant is passed as a an actual argument.
68
   Unknown - neither of the above.
69
 
70
   In order to compute the jump functions, we need the modify information for
71
   the formal parameters of methods.
72
 
73
   The jump function info, ipa_jump_func, is defined in ipa_edge
74
   structure (defined in ipa_prop.h and pointed to by cgraph_node->aux)
75
   The modify info, ipa_modify, is defined in ipa_node structure
76
   (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
77
 
78
   -ipcp_init_stage() is the first stage driver.
79
 
80
   Second stage - interprocedural analysis
81
   ========================================
82
   This phase does the interprocedural constant propagation.
83
   It computes for all formal parameters in the program
84
   their cval value that may be:
85
   TOP - unknown.
86
   BOTTOM - non constant.
87
   CONSTANT_TYPE - constant value.
88
 
89
   Cval of formal f will have a constant value if all callsites to this
90
   function have the same constant value passed to f.
91
 
92
   The cval info, ipcp_formal, is defined in ipa_node structure
93
   (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
94
 
95
   -ipcp_iterate_stage() is the second stage driver.
96
 
97
   Third phase - transformation of methods code
98
   ============================================
99
   Propagates the constant-valued formals into the function.
100
   For each method mt, whose parameters are consts, we create a clone/version.
101
 
102
   We use two ways to annotate the versioned function with the constant
103
   formal information:
104
   1. We insert an assignment statement 'parameter = const' at the beginning
105
   of the cloned method.
106
   2. For read-only formals whose address is not taken, we replace all uses
107
   of the formal with the constant (we provide versioning with an
108
   ipa_replace_map struct representing the trees we want to replace).
109
 
110
   We also need to modify some callsites to call to the cloned methods instead
111
   of the original ones. For a callsite passing an argument found to be a
112
   constant by IPCP, there are two different cases to handle:
113
   1. A constant is passed as an argument.
114
   2. A parameter (of the caller) passed as an argument (pass through argument).
115
 
116
   In the first case, the callsite in the original caller should be redirected
117
   to call the cloned callee.
118
   In the second case, both the caller and the callee have clones
119
   and the callsite of the cloned caller would be redirected to call to
120
   the cloned callee.
121
 
122
   The callgraph is updated accordingly.
123
 
124
   This update is done in two stages:
125
   First all cloned methods are created during a traversal of the callgraph,
126
   during which all callsites are redirected to call the cloned method.
127
   Then the callsites are traversed and updated as described above.
128
 
129
   -ipcp_insert_stage() is the third phase driver.
130
 
131
*/
132
 
133
#include "config.h"
134
#include "system.h"
135
#include "coretypes.h"
136
#include "tree.h"
137
#include "target.h"
138
#include "cgraph.h"
139
#include "ipa-prop.h"
140
#include "tree-flow.h"
141
#include "tree-pass.h"
142
#include "flags.h"
143
#include "timevar.h"
144
#include "diagnostic.h"
145
 
146
/* Get orig node field of ipa_node associated with method MT.  */
147
static inline struct cgraph_node *
148
ipcp_method_orig_node (struct cgraph_node *mt)
149
{
150
  return IPA_NODE_REF (mt)->ipcp_orig_node;
151
}
152
 
153
/* Return true if NODE is a cloned/versioned method.  */
154
static inline bool
155
ipcp_method_is_cloned (struct cgraph_node *node)
156
{
157
  return (ipcp_method_orig_node (node) != NULL);
158
}
159
 
160
/* Set ORIG_NODE in ipa_node associated with method NODE.  */
161
static inline void
162
ipcp_method_set_orig_node (struct cgraph_node *node,
163
                           struct cgraph_node *orig_node)
164
{
165
  IPA_NODE_REF (node)->ipcp_orig_node = orig_node;
166
}
167
 
168
/* Create ipa_node and its data structures for NEW_NODE.
169
   Set ORIG_NODE as the orig_node field in ipa_node.  */
170
static void
171
ipcp_cloned_create (struct cgraph_node *orig_node,
172
                    struct cgraph_node *new_node)
173
{
174
  ipa_node_create (new_node);
175
  ipcp_method_set_orig_node (new_node, orig_node);
176
  ipa_method_formal_compute_count (new_node);
177
  ipa_method_compute_tree_map (new_node);
178
}
179
 
180
/* Return cval_type field of CVAL.  */
181
static inline enum cvalue_type
182
ipcp_cval_get_cvalue_type (struct ipcp_formal *cval)
183
{
184
  return cval->cval_type;
185
}
186
 
187
/* Return scale for MT.  */
188
static inline gcov_type
189
ipcp_method_get_scale (struct cgraph_node *mt)
190
{
191
  return IPA_NODE_REF (mt)->count_scale;
192
}
193
 
194
/* Set COUNT as scale for MT.  */
195
static inline void
196
ipcp_method_set_scale (struct cgraph_node *node, gcov_type count)
197
{
198
  IPA_NODE_REF (node)->count_scale = count;
199
}
200
 
201
/* Set TYPE as cval_type field of CVAL.  */
202
static inline void
203
ipcp_cval_set_cvalue_type (struct ipcp_formal *cval, enum cvalue_type type)
204
{
205
  cval->cval_type = type;
206
}
207
 
208
/* Return cvalue field of CVAL.  */
209
static inline union parameter_info *
210
ipcp_cval_get_cvalue (struct ipcp_formal *cval)
211
{
212
  return &(cval->cvalue);
213
}
214
 
215
/* Set VALUE as cvalue field  CVAL.  */
216
static inline void
217
ipcp_cval_set_cvalue (struct ipcp_formal *cval, union parameter_info *value,
218
                      enum cvalue_type type)
219
{
220
  if (type == CONST_VALUE || type == CONST_VALUE_REF)
221
    cval->cvalue.value =  value->value;
222
}
223
 
224
/* Return whether TYPE is a constant type.  */
225
static bool
226
ipcp_type_is_const (enum cvalue_type type)
227
{
228
  if (type == CONST_VALUE || type == CONST_VALUE_REF)
229
    return true;
230
  else
231
    return false;
232
}
233
 
234
/* Return true if CONST_VAL1 and CONST_VAL2 are equal.  */
235
static inline bool
236
ipcp_cval_equal_cvalues (union parameter_info *const_val1,
237
                         union parameter_info *const_val2,
238
                         enum cvalue_type type1, enum cvalue_type type2)
239
{
240
  gcc_assert (ipcp_type_is_const (type1) && ipcp_type_is_const (type2));
241
  if (type1 != type2)
242
    return false;
243
 
244
  if (operand_equal_p (const_val1->value, const_val2->value, 0))
245
    return true;
246
 
247
  return false;
248
}
249
 
250
/* Compute Meet arithmetics:
251
   Meet (BOTTOM, x) = BOTTOM
252
   Meet (TOP,x) = x
253
   Meet (const_a,const_b) = BOTTOM,  if const_a != const_b.
254
   MEET (const_a,const_b) = const_a, if const_a == const_b.*/
255
static void
256
ipcp_cval_meet (struct ipcp_formal *cval, struct ipcp_formal *cval1,
257
                struct ipcp_formal *cval2)
258
{
259
  if (ipcp_cval_get_cvalue_type (cval1) == BOTTOM
260
      || ipcp_cval_get_cvalue_type (cval2) == BOTTOM)
261
    {
262
      ipcp_cval_set_cvalue_type (cval, BOTTOM);
263
      return;
264
    }
265
  if (ipcp_cval_get_cvalue_type (cval1) == TOP)
266
    {
267
      ipcp_cval_set_cvalue_type (cval, ipcp_cval_get_cvalue_type (cval2));
268
      ipcp_cval_set_cvalue (cval, ipcp_cval_get_cvalue (cval2),
269
                            ipcp_cval_get_cvalue_type (cval2));
270
      return;
271
    }
272
  if (ipcp_cval_get_cvalue_type (cval2) == TOP)
273
    {
274
      ipcp_cval_set_cvalue_type (cval, ipcp_cval_get_cvalue_type (cval1));
275
      ipcp_cval_set_cvalue (cval, ipcp_cval_get_cvalue (cval1),
276
                            ipcp_cval_get_cvalue_type (cval1));
277
      return;
278
    }
279
  if (!ipcp_cval_equal_cvalues (ipcp_cval_get_cvalue (cval1),
280
                                ipcp_cval_get_cvalue (cval2),
281
                                ipcp_cval_get_cvalue_type (cval1),
282
                                ipcp_cval_get_cvalue_type (cval2)))
283
    {
284
      ipcp_cval_set_cvalue_type (cval, BOTTOM);
285
      return;
286
    }
287
  ipcp_cval_set_cvalue_type (cval, ipcp_cval_get_cvalue_type (cval1));
288
  ipcp_cval_set_cvalue (cval, ipcp_cval_get_cvalue (cval1),
289
                        ipcp_cval_get_cvalue_type (cval1));
290
}
291
 
292
/* Return cval structure for the formal at index INFO_TYPE in MT.  */
293
static inline struct ipcp_formal *
294
ipcp_method_cval (struct cgraph_node *mt, int info_type)
295
{
296
  return &(IPA_NODE_REF (mt)->ipcp_cval[info_type]);
297
}
298
 
299
/* Given the jump function (TYPE, INFO_TYPE), compute a new value of CVAL.
300
   If TYPE is FORMAL_IPA_TYPE, the cval of the corresponding formal is
301
   drawn from MT.  */
302
static void
303
ipcp_cval_compute (struct ipcp_formal *cval, struct cgraph_node *mt,
304
                   enum jump_func_type type, union parameter_info *info_type)
305
{
306
  if (type == UNKNOWN_IPATYPE)
307
    ipcp_cval_set_cvalue_type (cval, BOTTOM);
308
  else if (type == CONST_IPATYPE)
309
    {
310
      ipcp_cval_set_cvalue_type (cval, CONST_VALUE);
311
      ipcp_cval_set_cvalue (cval, info_type, CONST_VALUE);
312
    }
313
  else if (type == CONST_IPATYPE_REF)
314
    {
315
      ipcp_cval_set_cvalue_type (cval, CONST_VALUE_REF);
316
      ipcp_cval_set_cvalue (cval, info_type, CONST_VALUE_REF);
317
    }
318
  else if (type == FORMAL_IPATYPE)
319
    {
320
      enum cvalue_type type =
321
        ipcp_cval_get_cvalue_type (ipcp_method_cval
322
                                   (mt, info_type->formal_id));
323
      ipcp_cval_set_cvalue_type (cval, type);
324
      ipcp_cval_set_cvalue (cval,
325
                            ipcp_cval_get_cvalue (ipcp_method_cval
326
                                                  (mt, info_type->formal_id)),
327
                            type);
328
    }
329
}
330
 
331
/* True when CVAL1 and CVAL2 values are not the same.  */
332
static bool
333
ipcp_cval_changed (struct ipcp_formal *cval1, struct ipcp_formal *cval2)
334
{
335
  if (ipcp_cval_get_cvalue_type (cval1) == ipcp_cval_get_cvalue_type (cval2))
336
    {
337
      if (ipcp_cval_get_cvalue_type (cval1) != CONST_VALUE &&
338
          ipcp_cval_get_cvalue_type (cval1) != CONST_VALUE_REF)
339
        return false;
340
      if (ipcp_cval_equal_cvalues (ipcp_cval_get_cvalue (cval1),
341
                                   ipcp_cval_get_cvalue (cval2),
342
                                   ipcp_cval_get_cvalue_type (cval1),
343
                                   ipcp_cval_get_cvalue_type (cval2)))
344
        return false;
345
    }
346
  return true;
347
}
348
 
349
/* Create cval structure for method MT.  */
350
static inline void
351
ipcp_formal_create (struct cgraph_node *mt)
352
{
353
  IPA_NODE_REF (mt)->ipcp_cval =
354
    XCNEWVEC (struct ipcp_formal, ipa_method_formal_count (mt));
355
}
356
 
357
/* Set cval structure of I-th formal of MT to CVAL.  */
358
static inline void
359
ipcp_method_cval_set (struct cgraph_node *mt, int i, struct ipcp_formal *cval)
360
{
361
  IPA_NODE_REF (mt)->ipcp_cval[i].cval_type = cval->cval_type;
362
  ipcp_cval_set_cvalue (ipcp_method_cval (mt, i),
363
                        ipcp_cval_get_cvalue (cval), cval->cval_type);
364
}
365
 
366
/* Set type of cval structure of formal I of MT to CVAL_TYPE1.  */
367
static inline void
368
ipcp_method_cval_set_cvalue_type (struct cgraph_node *mt, int i,
369
                                  enum cvalue_type cval_type1)
370
{
371
  IPA_NODE_REF (mt)->ipcp_cval[i].cval_type = cval_type1;
372
}
373
 
374
/* Print ipcp_cval data structures to F.  */
375
static void
376
ipcp_method_cval_print (FILE * f)
377
{
378
  struct cgraph_node *node;
379
  int i, count;
380
  tree cvalue;
381
 
382
  fprintf (f, "\nCVAL PRINT\n");
383
  for (node = cgraph_nodes; node; node = node->next)
384
    {
385
      fprintf (f, "Printing cvals %s:\n", cgraph_node_name (node));
386
      count = ipa_method_formal_count (node);
387
      for (i = 0; i < count; i++)
388
        {
389
          if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i))
390
              == CONST_VALUE
391
              || ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)) ==
392
              CONST_VALUE_REF)
393
            {
394
              fprintf (f, " param [%d]: ", i);
395
              fprintf (f, "type is CONST ");
396
              cvalue =
397
                ipcp_cval_get_cvalue (ipcp_method_cval (node, i))->
398
                  value;
399
              print_generic_expr (f, cvalue, 0);
400
              fprintf (f, "\n");
401
            }
402
          else if (ipcp_method_cval (node, i)->cval_type == TOP)
403
            fprintf (f, "param [%d]: type is TOP  \n", i);
404
          else
405
            fprintf (f, "param [%d]: type is BOTTOM  \n", i);
406
        }
407
    }
408
}
409
 
410
/* Initialize ipcp_cval array of MT with TOP values.
411
   All cvals for a method's formal parameters are initialized to BOTTOM
412
   The currently supported types are integer types, real types and
413
   Fortran constants (i.e. references to constants defined as
414
   const_decls). All other types are not analyzed and therefore are
415
   assigned with BOTTOM.  */
416
static void
417
ipcp_method_cval_init (struct cgraph_node *mt)
418
{
419
  int i;
420
  tree parm_tree;
421
 
422
  ipcp_formal_create (mt);
423
  for (i = 0; i < ipa_method_formal_count (mt); i++)
424
    {
425
      parm_tree = ipa_method_get_tree (mt, i);
426
      if (INTEGRAL_TYPE_P (TREE_TYPE (parm_tree))
427
          || SCALAR_FLOAT_TYPE_P (TREE_TYPE (parm_tree))
428
          || POINTER_TYPE_P (TREE_TYPE (parm_tree)))
429
        ipcp_method_cval_set_cvalue_type (mt, i, TOP);
430
      else
431
        ipcp_method_cval_set_cvalue_type (mt, i, BOTTOM);
432
    }
433
}
434
 
435
/* Create a new assignment statment and make
436
   it the first statement in the function FN
437
   tree.
438
   PARM1 is the lhs of the assignment and
439
   VAL is the rhs. */
440
static void
441
constant_val_insert (tree fn, tree parm1, tree val)
442
{
443
  struct function *func;
444
  tree init_stmt;
445
  edge e_step;
446
  edge_iterator ei;
447
 
448
  init_stmt = build2 (MODIFY_EXPR, void_type_node, parm1, val);
449
  func = DECL_STRUCT_FUNCTION (fn);
450
  cfun = func;
451
  current_function_decl = fn;
452
  if (ENTRY_BLOCK_PTR_FOR_FUNCTION (func)->succs)
453
    FOR_EACH_EDGE (e_step, ei, ENTRY_BLOCK_PTR_FOR_FUNCTION (func)->succs)
454
      bsi_insert_on_edge_immediate (e_step, init_stmt);
455
}
456
 
457
/* build INTEGER_CST tree with type TREE_TYPE and
458
   value according to CVALUE. Return the tree.   */
459
static tree
460
build_const_val (union parameter_info *cvalue, enum cvalue_type type,
461
                 tree tree_type)
462
{
463
  tree const_val = NULL;
464
 
465
  gcc_assert (ipcp_type_is_const (type));
466
  const_val = fold_convert (tree_type, cvalue->value);
467
  return const_val;
468
}
469
 
470
/* Build the tree representing the constant and call
471
   constant_val_insert().  */
472
static void
473
ipcp_propagate_const (struct cgraph_node *mt, int param,
474
                      union parameter_info *cvalue ,enum cvalue_type type)
475
{
476
  tree fndecl;
477
  tree const_val;
478
  tree parm_tree;
479
 
480
  if (dump_file)
481
    fprintf (dump_file, "propagating const to %s\n", cgraph_node_name (mt));
482
  fndecl = mt->decl;
483
  parm_tree = ipa_method_get_tree (mt, param);
484
  const_val = build_const_val (cvalue, type, TREE_TYPE (parm_tree));
485
  constant_val_insert (fndecl, parm_tree, const_val);
486
}
487
 
488
/* Compute the proper scale for NODE.  It is the ratio between
489
   the number of direct calls (represented on the incoming
490
   cgraph_edges) and sum of all invocations of NODE (represented
491
   as count in cgraph_node). */
492
static void
493
ipcp_method_compute_scale (struct cgraph_node *node)
494
{
495
  gcov_type sum;
496
  struct cgraph_edge *cs;
497
 
498
  sum = 0;
499
  /* Compute sum of all counts of callers. */
500
  for (cs = node->callers; cs != NULL; cs = cs->next_caller)
501
    sum += cs->count;
502
  if (node->count == 0)
503
    ipcp_method_set_scale (node, 0);
504
  else
505
    ipcp_method_set_scale (node, sum * REG_BR_PROB_BASE / node->count);
506
}
507
 
508
/* Initialization and computation of IPCP data structures.
509
   It is an intraprocedural
510
   analysis of methods, which gathers information to be propagated
511
   later on.  */
512
static void
513
ipcp_init_stage (void)
514
{
515
  struct cgraph_node *node;
516
  struct cgraph_edge *cs;
517
 
518
  for (node = cgraph_nodes; node; node = node->next)
519
    {
520
      ipa_method_formal_compute_count (node);
521
      ipa_method_compute_tree_map (node);
522
      ipcp_method_cval_init (node);
523
      ipa_method_compute_modify (node);
524
      ipcp_method_compute_scale (node);
525
    }
526
  for (node = cgraph_nodes; node; node = node->next)
527
    {
528
      /* building jump functions  */
529
      for (cs = node->callees; cs; cs = cs->next_callee)
530
        {
531
          ipa_callsite_compute_count (cs);
532
          if (ipa_callsite_param_count (cs)
533
              != ipa_method_formal_count (cs->callee))
534
            {
535
              /* Handle cases of functions with
536
                 a variable number of parameters.  */
537
              ipa_callsite_param_count_set (cs, 0);
538
              ipa_method_formal_count_set (cs->callee, 0);
539
            }
540
          else
541
            ipa_callsite_compute_param (cs);
542
        }
543
    }
544
}
545
 
546
/* Return true if there are some formal parameters whose value is TOP.
547
   Change their values to BOTTOM, since they weren't determined.  */
548
static bool
549
ipcp_after_propagate (void)
550
{
551
  int i, count;
552
  struct cgraph_node *node;
553
  bool prop_again;
554
 
555
  prop_again = false;
556
  for (node = cgraph_nodes; node; node = node->next)
557
    {
558
      count = ipa_method_formal_count (node);
559
      for (i = 0; i < count; i++)
560
        if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i)) == TOP)
561
          {
562
            prop_again = true;
563
            ipcp_method_cval_set_cvalue_type (node, i, BOTTOM);
564
          }
565
    }
566
  return prop_again;
567
}
568
 
569
/* Interprocedural analysis. The algorithm propagates constants from
570
   the caller's parameters to the callee's arguments.  */
571
static void
572
ipcp_propagate_stage (void)
573
{
574
  int i;
575
  struct ipcp_formal cval1 = { 0, {0} }, cval = { 0,{0} };
576
  struct ipcp_formal *cval2;
577
  struct cgraph_node *mt, *callee;
578
  struct cgraph_edge *cs;
579
  struct ipa_jump_func *jump_func;
580
  enum jump_func_type type;
581
  union parameter_info *info_type;
582
  ipa_methodlist_p wl;
583
  int count;
584
 
585
  /* Initialize worklist to contain all methods.  */
586
  wl = ipa_methodlist_init ();
587
  while (ipa_methodlist_not_empty (wl))
588
    {
589
      mt = ipa_remove_method (&wl);
590
      for (cs = mt->callees; cs; cs = cs->next_callee)
591
        {
592
          callee = ipa_callsite_callee (cs);
593
          count = ipa_callsite_param_count (cs);
594
          for (i = 0; i < count; i++)
595
            {
596
              jump_func = ipa_callsite_param (cs, i);
597
              type = get_type (jump_func);
598
              info_type = ipa_jf_get_info_type (jump_func);
599
              ipcp_cval_compute (&cval1, mt, type, info_type);
600
              cval2 = ipcp_method_cval (callee, i);
601
              ipcp_cval_meet (&cval, &cval1, cval2);
602
              if (ipcp_cval_changed (&cval, cval2))
603
                {
604
                  ipcp_method_cval_set (callee, i, &cval);
605
                  ipa_add_method (&wl, callee);
606
                }
607
            }
608
        }
609
    }
610
}
611
 
612
/* Call the constant propagation algorithm and re-call it if necessary
613
   (if there are undetermined values left).  */
614
static void
615
ipcp_iterate_stage (void)
616
{
617
  ipcp_propagate_stage ();
618
  if (ipcp_after_propagate ())
619
    /* Some cvals have changed from TOP to BOTTOM.
620
       This change should be propagated.  */
621
    ipcp_propagate_stage ();
622
}
623
 
624
/* Check conditions to forbid constant insertion to MT.  */
625
static bool
626
ipcp_method_dont_insert_const (struct cgraph_node *mt)
627
{
628
  /* ??? Handle pending sizes case.  */
629
  if (DECL_UNINLINABLE (mt->decl))
630
    return true;
631
  return false;
632
}
633
 
634
/* Print ipa_jump_func data structures to F.  */
635
static void
636
ipcp_callsite_param_print (FILE * f)
637
{
638
  struct cgraph_node *node;
639
  int i, count;
640
  struct cgraph_edge *cs;
641
  struct ipa_jump_func *jump_func;
642
  enum jump_func_type type;
643
  tree info_type;
644
 
645
  fprintf (f, "\nCALLSITE PARAM PRINT\n");
646
  for (node = cgraph_nodes; node; node = node->next)
647
    {
648
      for (cs = node->callees; cs; cs = cs->next_callee)
649
        {
650
          fprintf (f, "callsite  %s ", cgraph_node_name (node));
651
          fprintf (f, "-> %s :: \n", cgraph_node_name (cs->callee));
652
          count = ipa_callsite_param_count (cs);
653
          for (i = 0; i < count; i++)
654
            {
655
              jump_func = ipa_callsite_param (cs, i);
656
              type = get_type (jump_func);
657
 
658
              fprintf (f, " param %d: ", i);
659
              if (type == UNKNOWN_IPATYPE)
660
                fprintf (f, "UNKNOWN\n");
661
              else if (type == CONST_IPATYPE || type == CONST_IPATYPE_REF)
662
                {
663
                  info_type =
664
                    ipa_jf_get_info_type (jump_func)->value;
665
                  fprintf (f, "CONST : ");
666
                  print_generic_expr (f, info_type, 0);
667
                  fprintf (f, "\n");
668
                }
669
              else if (type == FORMAL_IPATYPE)
670
                {
671
                  fprintf (f, "FORMAL : ");
672
                  fprintf (f, "%d\n",
673
                           ipa_jf_get_info_type (jump_func)->formal_id);
674
                }
675
            }
676
        }
677
    }
678
}
679
 
680
/* Print count scale data structures.  */
681
static void
682
ipcp_method_scale_print (FILE * f)
683
{
684
  struct cgraph_node *node;
685
 
686
  for (node = cgraph_nodes; node; node = node->next)
687
    {
688
      fprintf (f, "printing scale for %s: ", cgraph_node_name (node));
689
      fprintf (f, "value is  " HOST_WIDE_INT_PRINT_DEC
690
               "  \n", (HOST_WIDE_INT) ipcp_method_get_scale (node));
691
    }
692
}
693
 
694
/* Print counts of all cgraph nodes.  */
695
static void
696
ipcp_profile_mt_count_print (FILE * f)
697
{
698
  struct cgraph_node *node;
699
 
700
  for (node = cgraph_nodes; node; node = node->next)
701
    {
702
      fprintf (f, "method %s: ", cgraph_node_name (node));
703
      fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC
704
               "  \n", (HOST_WIDE_INT) node->count);
705
    }
706
}
707
 
708
/* Print counts of all cgraph edges.  */
709
static void
710
ipcp_profile_cs_count_print (FILE * f)
711
{
712
  struct cgraph_node *node;
713
  struct cgraph_edge *cs;
714
 
715
  for (node = cgraph_nodes; node; node = node->next)
716
    {
717
      for (cs = node->callees; cs; cs = cs->next_callee)
718
        {
719
          fprintf (f, "%s -> %s ", cgraph_node_name (cs->caller),
720
                   cgraph_node_name (cs->callee));
721
          fprintf (f, "count is  " HOST_WIDE_INT_PRINT_DEC "  \n",
722
                   (HOST_WIDE_INT) cs->count);
723
        }
724
    }
725
}
726
 
727
/* Print all counts and probabilities of cfg edges of all methods.  */
728
static void
729
ipcp_profile_edge_print (FILE * f)
730
{
731
  struct cgraph_node *node;
732
  basic_block bb;
733
  edge_iterator ei;
734
  edge e;
735
 
736
  for (node = cgraph_nodes; node; node = node->next)
737
    {
738
      fprintf (f, "method %s: \n", cgraph_node_name (node));
739
      if (DECL_SAVED_TREE (node->decl))
740
        {
741
          bb =
742
            ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
743
          fprintf (f, "ENTRY: ");
744
          fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
745
                   " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency);
746
 
747
          if (bb->succs)
748
            FOR_EACH_EDGE (e, ei, bb->succs)
749
            {
750
              if (e->dest ==
751
                  EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
752
                                               (node->decl)))
753
                fprintf (f, "edge ENTRY -> EXIT,  Count");
754
              else
755
                fprintf (f, "edge ENTRY -> %d,  Count", e->dest->index);
756
              fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
757
                       " Prob %d\n", (HOST_WIDE_INT) e->count,
758
                       e->probability);
759
            }
760
          FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
761
          {
762
            fprintf (f, "bb[%d]: ", bb->index);
763
            fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
764
                     " %d\n", (HOST_WIDE_INT) bb->count, bb->frequency);
765
            FOR_EACH_EDGE (e, ei, bb->succs)
766
            {
767
              if (e->dest ==
768
                  EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
769
                                               (node->decl)))
770
                fprintf (f, "edge %d -> EXIT,  Count", e->src->index);
771
              else
772
                fprintf (f, "edge %d -> %d,  Count", e->src->index,
773
                         e->dest->index);
774
              fprintf (f, " " HOST_WIDE_INT_PRINT_DEC " Prob %d\n",
775
                       (HOST_WIDE_INT) e->count, e->probability);
776
            }
777
          }
778
        }
779
    }
780
}
781
 
782
/* Print counts and frequencies for all basic blocks of all methods.  */
783
static void
784
ipcp_profile_bb_print (FILE * f)
785
{
786
  basic_block bb;
787
  struct cgraph_node *node;
788
 
789
  for (node = cgraph_nodes; node; node = node->next)
790
    {
791
      fprintf (f, "method %s: \n", cgraph_node_name (node));
792
      if (DECL_SAVED_TREE (node->decl))
793
        {
794
          bb =
795
            ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
796
          fprintf (f, "ENTRY: Count");
797
          fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
798
                   " Frquency  %d\n", (HOST_WIDE_INT) bb->count,
799
                   bb->frequency);
800
 
801
          FOR_EACH_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
802
          {
803
            fprintf (f, "bb[%d]: Count", bb->index);
804
            fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
805
                     " Frequency %d\n", (HOST_WIDE_INT) bb->count,
806
                     bb->frequency);
807
          }
808
          bb =
809
            EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node->decl));
810
          fprintf (f, "EXIT: Count");
811
          fprintf (f, " " HOST_WIDE_INT_PRINT_DEC
812
                   " Frequency %d\n", (HOST_WIDE_INT) bb->count,
813
                   bb->frequency);
814
 
815
        }
816
    }
817
}
818
 
819
/* Print all IPCP data structures to F.  */
820
static void
821
ipcp_structures_print (FILE * f)
822
{
823
  ipcp_method_cval_print (f);
824
  ipcp_method_scale_print (f);
825
  ipa_method_tree_print (f);
826
  ipa_method_modify_print (f);
827
  ipcp_callsite_param_print (f);
828
}
829
 
830
/* Print profile info for all methods.  */
831
static void
832
ipcp_profile_print (FILE * f)
833
{
834
  fprintf (f, "\nNODE COUNTS :\n");
835
  ipcp_profile_mt_count_print (f);
836
  fprintf (f, "\nCS COUNTS stage:\n");
837
  ipcp_profile_cs_count_print (f);
838
  fprintf (f, "\nBB COUNTS and FREQUENCIES :\n");
839
  ipcp_profile_bb_print (f);
840
  fprintf (f, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
841
  ipcp_profile_edge_print (f);
842
}
843
 
844
/* Build and initialize ipa_replace_map struct
845
   according to TYPE. This struct is read by versioning, which
846
   operates according to the flags sent.  PARM_TREE is the
847
   formal's tree found to be constant.  CVALUE represents the constant.  */
848
static struct ipa_replace_map *
849
ipcp_replace_map_create (enum cvalue_type type, tree parm_tree,
850
                         union parameter_info *cvalue)
851
{
852
  struct ipa_replace_map *replace_map;
853
  tree const_val;
854
 
855
  replace_map = XCNEW (struct ipa_replace_map);
856
  gcc_assert (ipcp_type_is_const (type));
857
  if (type == CONST_VALUE_REF )
858
    {
859
      const_val =
860
        build_const_val (cvalue, type, TREE_TYPE (TREE_TYPE (parm_tree)));
861
      replace_map->old_tree = parm_tree;
862
      replace_map->new_tree = const_val;
863
      replace_map->replace_p = true;
864
      replace_map->ref_p = true;
865
    }
866
  else if (TREE_READONLY (parm_tree) && !TREE_ADDRESSABLE (parm_tree))
867
    {
868
      const_val = build_const_val (cvalue, type, TREE_TYPE (parm_tree));
869
      replace_map->old_tree = parm_tree;
870
      replace_map->new_tree = const_val;
871
      replace_map->replace_p = true;
872
      replace_map->ref_p = false;
873
    }
874
  else
875
    {
876
      replace_map->old_tree = NULL;
877
      replace_map->new_tree = NULL;
878
      replace_map->replace_p = false;
879
      replace_map->ref_p = false;
880
    }
881
 
882
  return replace_map;
883
}
884
 
885
/* Return true if this callsite should be redirected to
886
   the orig callee (instead of the cloned one).  */
887
static bool
888
ipcp_redirect (struct cgraph_edge *cs)
889
{
890
  struct cgraph_node *caller, *callee, *orig_callee;
891
  int i, count;
892
  struct ipa_jump_func *jump_func;
893
  enum jump_func_type type;
894
  enum cvalue_type cval_type;
895
 
896
  caller = cs->caller;
897
  callee = cs->callee;
898
  orig_callee = ipcp_method_orig_node (callee);
899
  count = ipa_method_formal_count (orig_callee);
900
  for (i = 0; i < count; i++)
901
    {
902
      cval_type =
903
        ipcp_cval_get_cvalue_type (ipcp_method_cval (orig_callee, i));
904
      if (ipcp_type_is_const (cval_type))
905
        {
906
          jump_func = ipa_callsite_param (cs, i);
907
          type = get_type (jump_func);
908
          if (type != CONST_IPATYPE
909
              && type != CONST_IPATYPE_REF)
910
            return true;
911
        }
912
    }
913
 
914
  return false;
915
}
916
 
917
/* Fix the callsites and the callgraph after function cloning was done.  */
918
static void
919
ipcp_update_callgraph (void)
920
{
921
  struct cgraph_node *node, *orig_callee;
922
  struct cgraph_edge *cs;
923
 
924
  for (node = cgraph_nodes; node; node = node->next)
925
    {
926
      /* want to fix only original nodes  */
927
      if (ipcp_method_is_cloned (node))
928
        continue;
929
      for (cs = node->callees; cs; cs = cs->next_callee)
930
        if (ipcp_method_is_cloned (cs->callee))
931
          {
932
            /* Callee is a cloned node  */
933
            orig_callee = ipcp_method_orig_node (cs->callee);
934
            if (ipcp_redirect (cs))
935
              {
936
                cgraph_redirect_edge_callee (cs, orig_callee);
937
                TREE_OPERAND (TREE_OPERAND
938
                              (get_call_expr_in (cs->call_stmt), 0), 0) =
939
                  orig_callee->decl;
940
              }
941
          }
942
    }
943
}
944
 
945
/* Update all cfg basic blocks in NODE according to SCALE.  */
946
static void
947
ipcp_update_bb_counts (struct cgraph_node *node, gcov_type scale)
948
{
949
  basic_block bb;
950
 
951
  FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
952
    bb->count = bb->count * scale / REG_BR_PROB_BASE;
953
}
954
 
955
/* Update all cfg edges in NODE according to SCALE.  */
956
static void
957
ipcp_update_edges_counts (struct cgraph_node *node, gcov_type scale)
958
{
959
  basic_block bb;
960
  edge_iterator ei;
961
  edge e;
962
 
963
  FOR_ALL_BB_FN (bb, DECL_STRUCT_FUNCTION (node->decl))
964
    FOR_EACH_EDGE (e, ei, bb->succs)
965
    e->count = e->count * scale / REG_BR_PROB_BASE;
966
}
967
 
968
/* Update profiling info for versioned methods and the
969
   methods they were versioned from.  */
970
static void
971
ipcp_update_profiling (void)
972
{
973
  struct cgraph_node *node, *orig_node;
974
  gcov_type scale, scale_complement;
975
  struct cgraph_edge *cs;
976
 
977
  for (node = cgraph_nodes; node; node = node->next)
978
    {
979
      if (ipcp_method_is_cloned (node))
980
        {
981
          orig_node = ipcp_method_orig_node (node);
982
          scale = ipcp_method_get_scale (orig_node);
983
          node->count = orig_node->count * scale / REG_BR_PROB_BASE;
984
          scale_complement = REG_BR_PROB_BASE - scale;
985
          orig_node->count =
986
            orig_node->count * scale_complement / REG_BR_PROB_BASE;
987
          for (cs = node->callees; cs; cs = cs->next_callee)
988
            cs->count = cs->count * scale / REG_BR_PROB_BASE;
989
          for (cs = orig_node->callees; cs; cs = cs->next_callee)
990
            cs->count = cs->count * scale_complement / REG_BR_PROB_BASE;
991
          ipcp_update_bb_counts (node, scale);
992
          ipcp_update_bb_counts (orig_node, scale_complement);
993
          ipcp_update_edges_counts (node, scale);
994
          ipcp_update_edges_counts (orig_node, scale_complement);
995
        }
996
    }
997
}
998
 
999
/* Propagate the constant parameters found by ipcp_iterate_stage()
1000
   to the function's code.  */
1001
static void
1002
ipcp_insert_stage (void)
1003
{
1004
  struct cgraph_node *node, *node1 = NULL;
1005
  int i, const_param;
1006
  union parameter_info *cvalue;
1007
  VEC(cgraph_edge_p,heap) *redirect_callers;
1008
  varray_type replace_trees;
1009
  struct cgraph_edge *cs;
1010
  int node_callers, count;
1011
  tree parm_tree;
1012
  enum cvalue_type type;
1013
  struct ipa_replace_map *replace_param;
1014
 
1015
  for (node = cgraph_nodes; node; node = node->next)
1016
    {
1017
      /* Propagation of the constant is forbidden in
1018
         certain conditions.  */
1019
      if (ipcp_method_dont_insert_const (node))
1020
        continue;
1021
      const_param = 0;
1022
      count = ipa_method_formal_count (node);
1023
      for (i = 0; i < count; i++)
1024
        {
1025
          type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i));
1026
          if (ipcp_type_is_const (type))
1027
            const_param++;
1028
        }
1029
      if (const_param == 0)
1030
        continue;
1031
      VARRAY_GENERIC_PTR_INIT (replace_trees, const_param, "replace_trees");
1032
      for (i = 0; i < count; i++)
1033
        {
1034
          type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i));
1035
          if (ipcp_type_is_const (type))
1036
            {
1037
              cvalue = ipcp_cval_get_cvalue (ipcp_method_cval (node, i));
1038
              parm_tree = ipa_method_get_tree (node, i);
1039
              replace_param =
1040
                ipcp_replace_map_create (type, parm_tree, cvalue);
1041
              VARRAY_PUSH_GENERIC_PTR (replace_trees, replace_param);
1042
            }
1043
        }
1044
      /* Compute how many callers node has.  */
1045
      node_callers = 0;
1046
      for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1047
        node_callers++;
1048
      redirect_callers = VEC_alloc (cgraph_edge_p, heap, node_callers);
1049
      for (cs = node->callers; cs != NULL; cs = cs->next_caller)
1050
        VEC_quick_push (cgraph_edge_p, redirect_callers, cs);
1051
      /* Redirecting all the callers of the node to the
1052
         new versioned node.  */
1053
      node1 =
1054
        cgraph_function_versioning (node, redirect_callers, replace_trees);
1055
      VEC_free (cgraph_edge_p, heap, redirect_callers);
1056
      VARRAY_CLEAR (replace_trees);
1057
      if (node1 == NULL)
1058
        continue;
1059
      if (dump_file)
1060
        fprintf (dump_file, "versioned function %s\n",
1061
                 cgraph_node_name (node));
1062
      ipcp_cloned_create (node, node1);
1063
      for (i = 0; i < count; i++)
1064
        {
1065
          type = ipcp_cval_get_cvalue_type (ipcp_method_cval (node, i));
1066
          if (ipcp_type_is_const (type))
1067
            {
1068
              cvalue = ipcp_cval_get_cvalue (ipcp_method_cval (node, i));
1069
              parm_tree = ipa_method_get_tree (node, i);
1070
              if (type != CONST_VALUE_REF
1071
                  && !TREE_READONLY (parm_tree))
1072
                ipcp_propagate_const (node1, i, cvalue, type);
1073
            }
1074
        }
1075
    }
1076
  ipcp_update_callgraph ();
1077
  ipcp_update_profiling ();
1078
}
1079
 
1080
/* The IPCP driver.  */
1081
unsigned int
1082
ipcp_driver (void)
1083
{
1084
  if (dump_file)
1085
    fprintf (dump_file, "\nIPA constant propagation start:\n");
1086
  ipa_nodes_create ();
1087
  ipa_edges_create ();
1088
  /* 1. Call the init stage to initialize
1089
     the ipa_node and ipa_edge structures.  */
1090
  ipcp_init_stage ();
1091
  if (dump_file)
1092
    {
1093
      fprintf (dump_file, "\nIPA structures before propagation:\n");
1094
      ipcp_structures_print (dump_file);
1095
    }
1096
  /* 2. Do the interprocedural propagation.  */
1097
  ipcp_iterate_stage ();
1098
  if (dump_file)
1099
    {
1100
      fprintf (dump_file, "\nIPA structures after propagation:\n");
1101
      ipcp_structures_print (dump_file);
1102
      fprintf (dump_file, "\nProfiling info before insert stage:\n");
1103
      ipcp_profile_print (dump_file);
1104
    }
1105
  /* 3. Insert the constants found to the functions.  */
1106
  ipcp_insert_stage ();
1107
  if (dump_file)
1108
    {
1109
      fprintf (dump_file, "\nProfiling info after insert stage:\n");
1110
      ipcp_profile_print (dump_file);
1111
    }
1112
  /* Free all IPCP structures.  */
1113
  ipa_free ();
1114
  ipa_nodes_free ();
1115
  ipa_edges_free ();
1116
  if (dump_file)
1117
    fprintf (dump_file, "\nIPA constant propagation end\n");
1118
  cgraph_remove_unreachable_nodes (true, NULL);
1119
  return 0;
1120
}
1121
 
1122
/* Gate for IPCP optimization.  */
1123
static bool
1124
cgraph_gate_cp (void)
1125
{
1126
  return flag_ipa_cp;
1127
}
1128
 
1129
struct tree_opt_pass pass_ipa_cp = {
1130
  "cp",                         /* name */
1131
  cgraph_gate_cp,               /* gate */
1132
  ipcp_driver,                  /* execute */
1133
  NULL,                         /* sub */
1134
  NULL,                         /* next */
1135
  0,                             /* static_pass_number */
1136
  TV_IPA_CONSTANT_PROP,         /* tv_id */
1137
  0,                             /* properties_required */
1138
  PROP_trees,                   /* properties_provided */
1139
  0,                             /* properties_destroyed */
1140
  0,                             /* todo_flags_start */
1141
  TODO_dump_cgraph | TODO_dump_func,    /* todo_flags_finish */
1142
 
1143
};

powered by: WebSVN 2.1.0

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