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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [ipa-cp.c] - Blame information for rev 692

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

Line No. Rev Author Line
1 684 jeremybenn
/* Interprocedural constant propagation
2
   Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
3
   Free Software Foundation, Inc.
4
 
5
   Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
6
   <mjambor@suse.cz>
7
 
8
This file is part of GCC.
9
 
10
GCC is free software; you can redistribute it and/or modify it under
11
the terms of the GNU General Public License as published by the Free
12
Software Foundation; either version 3, or (at your option) any later
13
version.
14
 
15
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16
WARRANTY; without even the implied warranty of MERCHANTABILITY or
17
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
18
for more details.
19
 
20
You should have received a copy of the GNU General Public License
21
along with GCC; see the file COPYING3.  If not see
22
<http://www.gnu.org/licenses/>.  */
23
 
24
/* Interprocedural constant propagation (IPA-CP).
25
 
26
   The goal of this transformation is to
27
 
28
   1) discover functions which are always invoked with some arguments with the
29
      same known constant values and modify the functions so that the
30
      subsequent optimizations can take advantage of the knowledge, and
31
 
32
   2) partial specialization - create specialized versions of functions
33
      transformed in this way if some parameters are known constants only in
34
      certain contexts but the estimated tradeoff between speedup and cost size
35
      is deemed good.
36
 
37
   The algorithm also propagates types and attempts to perform type based
38
   devirtualization.  Types are propagated much like constants.
39
 
40
   The algorithm basically consists of three stages.  In the first, functions
41
   are analyzed one at a time and jump functions are constructed for all known
42
   call-sites.  In the second phase, the pass propagates information from the
43
   jump functions across the call to reveal what values are available at what
44
   call sites, performs estimations of effects of known values on functions and
45
   their callees, and finally decides what specialized extra versions should be
46
   created.  In the third, the special versions materialize and appropriate
47
   calls are redirected.
48
 
49
   The algorithm used is to a certain extent based on "Interprocedural Constant
50
   Propagation", by David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon,
51
   Comp86, pg 152-161 and "A Methodology for Procedure Cloning" by Keith D
52
   Cooper, Mary W. Hall, and Ken Kennedy.
53
 
54
 
55
   First stage - intraprocedural analysis
56
   =======================================
57
 
58
   This phase computes jump_function and modification flags.
59
 
60
   A jump function for a call-site represents the values passed as an actual
61
   arguments of a given call-site. In principle, there are three types of
62
   values:
63
 
64
   Pass through - the caller's formal parameter is passed as an actual
65
                  argument, plus an operation on it can be performed.
66
   Constant - a constant is passed as an actual argument.
67
   Unknown - neither of the above.
68
 
69
   All jump function types are described in detail in ipa-prop.h, together with
70
   the data structures that represent them and methods of accessing them.
71
 
72
   ipcp_generate_summary() is the main function of the first stage.
73
 
74
   Second stage - interprocedural analysis
75
   ========================================
76
 
77
   This stage is itself divided into two phases.  In the first, we propagate
78
   known values over the call graph, in the second, we make cloning decisions.
79
   It uses a different algorithm than the original Callahan's paper.
80
 
81
   First, we traverse the functions topologically from callers to callees and,
82
   for each strongly connected component (SCC), we propagate constants
83
   according to previously computed jump functions.  We also record what known
84
   values depend on other known values and estimate local effects.  Finally, we
85
   propagate cumulative information about these effects from dependant values
86
   to those on which they depend.
87
 
88
   Second, we again traverse the call graph in the same topological order and
89
   make clones for functions which we know are called with the same values in
90
   all contexts and decide about extra specialized clones of functions just for
91
   some contexts - these decisions are based on both local estimates and
92
   cumulative estimates propagated from callees.
93
 
94
   ipcp_propagate_stage() and ipcp_decision_stage() together constitute the
95
   third stage.
96
 
97
   Third phase - materialization of clones, call statement updates.
98
   ============================================
99
 
100
   This stage is currently performed by call graph code (mainly in cgraphunit.c
101
   and tree-inline.c) according to instructions inserted to the call graph by
102
   the second stage.  */
103
 
104
#include "config.h"
105
#include "system.h"
106
#include "coretypes.h"
107
#include "tree.h"
108
#include "target.h"
109
#include "gimple.h"
110
#include "cgraph.h"
111
#include "ipa-prop.h"
112
#include "tree-flow.h"
113
#include "tree-pass.h"
114
#include "flags.h"
115
#include "timevar.h"
116
#include "diagnostic.h"
117
#include "tree-pretty-print.h"
118
#include "tree-dump.h"
119
#include "tree-inline.h"
120
#include "fibheap.h"
121
#include "params.h"
122
#include "ipa-inline.h"
123
#include "ipa-utils.h"
124
 
125
struct ipcp_value;
126
 
127
/* Describes a particular source for an IPA-CP value.  */
128
 
129
struct ipcp_value_source
130
{
131
  /* The incoming edge that brought the value.  */
132
  struct cgraph_edge *cs;
133
  /* If the jump function that resulted into his value was a pass-through or an
134
     ancestor, this is the ipcp_value of the caller from which the described
135
     value has been derived.  Otherwise it is NULL.  */
136
  struct ipcp_value *val;
137
  /* Next pointer in a linked list of sources of a value.  */
138
  struct ipcp_value_source *next;
139
  /* If the jump function that resulted into his value was a pass-through or an
140
     ancestor, this is the index of the parameter of the caller the jump
141
     function references.  */
142
  int index;
143
};
144
 
145
/* Describes one particular value stored in struct ipcp_lattice.  */
146
 
147
struct ipcp_value
148
{
149
  /* The actual value for the given parameter.  This is either an IPA invariant
150
     or a TREE_BINFO describing a type that can be used for
151
     devirtualization.  */
152
  tree value;
153
  /* The list of sources from which this value originates.  */
154
  struct ipcp_value_source *sources;
155
  /* Next pointers in a linked list of all values in a lattice.  */
156
  struct ipcp_value *next;
157
  /* Next pointers in a linked list of values in a strongly connected component
158
     of values. */
159
  struct ipcp_value *scc_next;
160
  /* Next pointers in a linked list of SCCs of values sorted topologically
161
     according their sources.  */
162
  struct ipcp_value  *topo_next;
163
  /* A specialized node created for this value, NULL if none has been (so far)
164
     created.  */
165
  struct cgraph_node *spec_node;
166
  /* Depth first search number and low link for topological sorting of
167
     values.  */
168
  int dfs, low_link;
169
  /* Time benefit and size cost that specializing the function for this value
170
     would bring about in this function alone.  */
171
  int local_time_benefit, local_size_cost;
172
  /* Time benefit and size cost that specializing the function for this value
173
     can bring about in it's callees (transitively).  */
174
  int prop_time_benefit, prop_size_cost;
175
  /* True if this valye is currently on the topo-sort stack.  */
176
  bool on_stack;
177
};
178
 
179
/* Allocation pools for values and their sources in ipa-cp.  */
180
 
181
alloc_pool ipcp_values_pool;
182
alloc_pool ipcp_sources_pool;
183
 
184
/* Lattice describing potential values of a formal parameter of a function and
185
   some of their other properties.  TOP is represented by a lattice with zero
186
   values and with contains_variable and bottom flags cleared.  BOTTOM is
187
   represented by a lattice with the bottom flag set.  In that case, values and
188
   contains_variable flag should be disregarded.  */
189
 
190
struct ipcp_lattice
191
{
192
  /* The list of known values and types in this lattice.  Note that values are
193
     not deallocated if a lattice is set to bottom because there may be value
194
     sources referencing them.  */
195
  struct ipcp_value *values;
196
  /* Number of known values and types in this lattice.  */
197
  int values_count;
198
  /* The lattice contains a variable component  (in addition to values).  */
199
  bool contains_variable;
200
  /* The value of the lattice is bottom (i.e. variable and unusable for any
201
     propagation).  */
202
  bool bottom;
203
  /* There is a virtual call based on this parameter.  */
204
  bool virt_call;
205
};
206
 
207
/* Maximal count found in program.  */
208
 
209
static gcov_type max_count;
210
 
211
/* Original overall size of the program.  */
212
 
213
static long overall_size, max_new_size;
214
 
215
/* Head of the linked list of topologically sorted values. */
216
 
217
static struct ipcp_value *values_topo;
218
 
219
/* Return the lattice corresponding to the Ith formal parameter of the function
220
   described by INFO.  */
221
static inline struct ipcp_lattice *
222
ipa_get_lattice (struct ipa_node_params *info, int i)
223
{
224
  gcc_assert (i >= 0 && i < ipa_get_param_count (info));
225
  gcc_checking_assert (!info->ipcp_orig_node);
226
  gcc_checking_assert (info->lattices);
227
  return &(info->lattices[i]);
228
}
229
 
230
/* Return whether LAT is a lattice with a single constant and without an
231
   undefined value.  */
232
 
233
static inline bool
234
ipa_lat_is_single_const (struct ipcp_lattice *lat)
235
{
236
  if (lat->bottom
237
      || lat->contains_variable
238
      || lat->values_count != 1)
239
    return false;
240
  else
241
    return true;
242
}
243
 
244
/* Return true iff the CS is an edge within a strongly connected component as
245
   computed by ipa_reduced_postorder.  */
246
 
247
static inline bool
248
edge_within_scc (struct cgraph_edge *cs)
249
{
250
  struct ipa_dfs_info *caller_dfs = (struct ipa_dfs_info *) cs->caller->aux;
251
  struct ipa_dfs_info *callee_dfs;
252
  struct cgraph_node *callee = cgraph_function_node (cs->callee, NULL);
253
 
254
  callee_dfs = (struct ipa_dfs_info *) callee->aux;
255
  return (caller_dfs
256
          && callee_dfs
257
          && caller_dfs->scc_no == callee_dfs->scc_no);
258
}
259
 
260
/* Print V which is extracted from a value in a lattice to F.  */
261
 
262
static void
263
print_ipcp_constant_value (FILE * f, tree v)
264
{
265
  if (TREE_CODE (v) == TREE_BINFO)
266
    {
267
      fprintf (f, "BINFO ");
268
      print_generic_expr (f, BINFO_TYPE (v), 0);
269
    }
270
  else if (TREE_CODE (v) == ADDR_EXPR
271
           && TREE_CODE (TREE_OPERAND (v, 0)) == CONST_DECL)
272
    {
273
      fprintf (f, "& ");
274
      print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (v, 0)), 0);
275
    }
276
  else
277
    print_generic_expr (f, v, 0);
278
}
279
 
280
/* Print all ipcp_lattices of all functions to F.  */
281
 
282
static void
283
print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits)
284
{
285
  struct cgraph_node *node;
286
  int i, count;
287
 
288
  fprintf (f, "\nLattices:\n");
289
  FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
290
    {
291
      struct ipa_node_params *info;
292
 
293
      info = IPA_NODE_REF (node);
294
      fprintf (f, "  Node: %s/%i:\n", cgraph_node_name (node), node->uid);
295
      count = ipa_get_param_count (info);
296
      for (i = 0; i < count; i++)
297
        {
298
          struct ipcp_lattice *lat = ipa_get_lattice (info, i);
299
          struct ipcp_value *val;
300
          bool prev = false;
301
 
302
          fprintf (f, "    param [%d]: ", i);
303
          if (lat->bottom)
304
            {
305
              fprintf (f, "BOTTOM\n");
306
              continue;
307
            }
308
 
309
          if (!lat->values_count && !lat->contains_variable)
310
            {
311
              fprintf (f, "TOP\n");
312
              continue;
313
            }
314
 
315
          if (lat->contains_variable)
316
            {
317
              fprintf (f, "VARIABLE");
318
              prev = true;
319
              if (dump_benefits)
320
                fprintf (f, "\n");
321
            }
322
 
323
          for (val = lat->values; val; val = val->next)
324
            {
325
              if (dump_benefits && prev)
326
                fprintf (f, "               ");
327
              else if (!dump_benefits && prev)
328
                fprintf (f, ", ");
329
              else
330
                prev = true;
331
 
332
              print_ipcp_constant_value (f, val->value);
333
 
334
              if (dump_sources)
335
                {
336
                  struct ipcp_value_source *s;
337
 
338
                  fprintf (f, " [from:");
339
                  for (s = val->sources; s; s = s->next)
340
                    fprintf (f, " %i(%i)", s->cs->caller->uid,s->cs->frequency);
341
                  fprintf (f, "]");
342
                }
343
 
344
              if (dump_benefits)
345
                fprintf (f, " [loc_time: %i, loc_size: %i, "
346
                         "prop_time: %i, prop_size: %i]\n",
347
                         val->local_time_benefit, val->local_size_cost,
348
                         val->prop_time_benefit, val->prop_size_cost);
349
            }
350
          if (!dump_benefits)
351
            fprintf (f, "\n");
352
        }
353
    }
354
}
355
 
356
/* Determine whether it is at all technically possible to create clones of NODE
357
   and store this information in the ipa_node_params structure associated
358
   with NODE.  */
359
 
360
static void
361
determine_versionability (struct cgraph_node *node)
362
{
363
  const char *reason = NULL;
364
 
365
  /* There are a number of generic reasons functions cannot be versioned.  We
366
     also cannot remove parameters if there are type attributes such as fnspec
367
     present.  */
368
  if (node->alias || node->thunk.thunk_p)
369
    reason = "alias or thunk";
370
  else if (!node->local.versionable)
371
    reason = "not a tree_versionable_function";
372
  else if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
373
    reason = "insufficient body availability";
374
 
375
  if (reason && dump_file && !node->alias && !node->thunk.thunk_p)
376
    fprintf (dump_file, "Function %s/%i is not versionable, reason: %s.\n",
377
             cgraph_node_name (node), node->uid, reason);
378
 
379
  node->local.versionable = (reason == NULL);
380
}
381
 
382
/* Return true if it is at all technically possible to create clones of a
383
   NODE.  */
384
 
385
static bool
386
ipcp_versionable_function_p (struct cgraph_node *node)
387
{
388
  return node->local.versionable;
389
}
390
 
391
/* Structure holding accumulated information about callers of a node.  */
392
 
393
struct caller_statistics
394
{
395
  gcov_type count_sum;
396
  int n_calls, n_hot_calls, freq_sum;
397
};
398
 
399
/* Initialize fields of STAT to zeroes.  */
400
 
401
static inline void
402
init_caller_stats (struct caller_statistics *stats)
403
{
404
  stats->count_sum = 0;
405
  stats->n_calls = 0;
406
  stats->n_hot_calls = 0;
407
  stats->freq_sum = 0;
408
}
409
 
410
/* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
411
   non-thunk incoming edges to NODE.  */
412
 
413
static bool
414
gather_caller_stats (struct cgraph_node *node, void *data)
415
{
416
  struct caller_statistics *stats = (struct caller_statistics *) data;
417
  struct cgraph_edge *cs;
418
 
419
  for (cs = node->callers; cs; cs = cs->next_caller)
420
    if (cs->caller->thunk.thunk_p)
421
      cgraph_for_node_and_aliases (cs->caller, gather_caller_stats,
422
                                   stats, false);
423
    else
424
      {
425
        stats->count_sum += cs->count;
426
        stats->freq_sum += cs->frequency;
427
        stats->n_calls++;
428
        if (cgraph_maybe_hot_edge_p (cs))
429
          stats->n_hot_calls ++;
430
      }
431
  return false;
432
 
433
}
434
 
435
/* Return true if this NODE is viable candidate for cloning.  */
436
 
437
static bool
438
ipcp_cloning_candidate_p (struct cgraph_node *node)
439
{
440
  struct caller_statistics stats;
441
 
442
  gcc_checking_assert (cgraph_function_with_gimple_body_p (node));
443
 
444
  if (!flag_ipa_cp_clone)
445
    {
446
      if (dump_file)
447
        fprintf (dump_file, "Not considering %s for cloning; "
448
                 "-fipa-cp-clone disabled.\n",
449
                 cgraph_node_name (node));
450
      return false;
451
    }
452
 
453
  if (!optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
454
    {
455
      if (dump_file)
456
        fprintf (dump_file, "Not considering %s for cloning; "
457
                 "optimizing it for size.\n",
458
                 cgraph_node_name (node));
459
      return false;
460
    }
461
 
462
  init_caller_stats (&stats);
463
  cgraph_for_node_and_aliases (node, gather_caller_stats, &stats, false);
464
 
465
  if (inline_summary (node)->self_size < stats.n_calls)
466
    {
467
      if (dump_file)
468
        fprintf (dump_file, "Considering %s for cloning; code might shrink.\n",
469
                 cgraph_node_name (node));
470
      return true;
471
    }
472
 
473
  /* When profile is available and function is hot, propagate into it even if
474
     calls seems cold; constant propagation can improve function's speed
475
     significantly.  */
476
  if (max_count)
477
    {
478
      if (stats.count_sum > node->count * 90 / 100)
479
        {
480
          if (dump_file)
481
            fprintf (dump_file, "Considering %s for cloning; "
482
                     "usually called directly.\n",
483
                     cgraph_node_name (node));
484
          return true;
485
        }
486
    }
487
  if (!stats.n_hot_calls)
488
    {
489
      if (dump_file)
490
        fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
491
                 cgraph_node_name (node));
492
      return false;
493
    }
494
  if (dump_file)
495
    fprintf (dump_file, "Considering %s for cloning.\n",
496
             cgraph_node_name (node));
497
  return true;
498
}
499
 
500
/* Arrays representing a topological ordering of call graph nodes and a stack
501
   of noes used during constant propagation.  */
502
 
503
struct topo_info
504
{
505
  struct cgraph_node **order;
506
  struct cgraph_node **stack;
507
  int nnodes, stack_top;
508
};
509
 
510
/* Allocate the arrays in TOPO and topologically sort the nodes into order.  */
511
 
512
static void
513
build_toporder_info (struct topo_info *topo)
514
{
515
  topo->order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
516
  topo->stack = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
517
  topo->stack_top = 0;
518
  topo->nnodes = ipa_reduced_postorder (topo->order, true, true, NULL);
519
}
520
 
521
/* Free information about strongly connected components and the arrays in
522
   TOPO.  */
523
 
524
static void
525
free_toporder_info (struct topo_info *topo)
526
{
527
  ipa_free_postorder_info ();
528
  free (topo->order);
529
  free (topo->stack);
530
}
531
 
532
/* Add NODE to the stack in TOPO, unless it is already there.  */
533
 
534
static inline void
535
push_node_to_stack (struct topo_info *topo, struct cgraph_node *node)
536
{
537
  struct ipa_node_params *info = IPA_NODE_REF (node);
538
  if (info->node_enqueued)
539
    return;
540
  info->node_enqueued = 1;
541
  topo->stack[topo->stack_top++] = node;
542
}
543
 
544
/* Pop a node from the stack in TOPO and return it or return NULL if the stack
545
   is empty.  */
546
 
547
static struct cgraph_node *
548
pop_node_from_stack (struct topo_info *topo)
549
{
550
  if (topo->stack_top)
551
    {
552
      struct cgraph_node *node;
553
      topo->stack_top--;
554
      node = topo->stack[topo->stack_top];
555
      IPA_NODE_REF (node)->node_enqueued = 0;
556
      return node;
557
    }
558
  else
559
    return NULL;
560
}
561
 
562
/* Set lattice LAT to bottom and return true if it previously was not set as
563
   such.  */
564
 
565
static inline bool
566
set_lattice_to_bottom (struct ipcp_lattice *lat)
567
{
568
  bool ret = !lat->bottom;
569
  lat->bottom = true;
570
  return ret;
571
}
572
 
573
/* Mark lattice as containing an unknown value and return true if it previously
574
   was not marked as such.  */
575
 
576
static inline bool
577
set_lattice_contains_variable (struct ipcp_lattice *lat)
578
{
579
  bool ret = !lat->contains_variable;
580
  lat->contains_variable = true;
581
  return ret;
582
}
583
 
584
/* Initialize ipcp_lattices.  */
585
 
586
static void
587
initialize_node_lattices (struct cgraph_node *node)
588
{
589
  struct ipa_node_params *info = IPA_NODE_REF (node);
590
  struct cgraph_edge *ie;
591
  bool disable = false, variable = false;
592
  int i;
593
 
594
  gcc_checking_assert (cgraph_function_with_gimple_body_p (node));
595
  if (!node->local.local)
596
    {
597
      /* When cloning is allowed, we can assume that externally visible
598
         functions are not called.  We will compensate this by cloning
599
         later.  */
600
      if (ipcp_versionable_function_p (node)
601
          && ipcp_cloning_candidate_p (node))
602
        variable = true;
603
      else
604
        disable = true;
605
    }
606
 
607
  if (disable || variable)
608
    {
609
      for (i = 0; i < ipa_get_param_count (info) ; i++)
610
        {
611
          struct ipcp_lattice *lat = ipa_get_lattice (info, i);
612
          if (disable)
613
            set_lattice_to_bottom (lat);
614
          else
615
            set_lattice_contains_variable (lat);
616
        }
617
      if (dump_file && (dump_flags & TDF_DETAILS)
618
          && node->alias && node->thunk.thunk_p)
619
        fprintf (dump_file, "Marking all lattices of %s/%i as %s\n",
620
                 cgraph_node_name (node), node->uid,
621
                 disable ? "BOTTOM" : "VARIABLE");
622
    }
623
 
624
  for (ie = node->indirect_calls; ie; ie = ie->next_callee)
625
    if (ie->indirect_info->polymorphic)
626
      {
627
        gcc_checking_assert (ie->indirect_info->param_index >= 0);
628
        ipa_get_lattice (info, ie->indirect_info->param_index)->virt_call = 1;
629
      }
630
}
631
 
632
/* Return the result of a (possibly arithmetic) pass through jump function
633
   JFUNC on the constant value INPUT.  Return NULL_TREE if that cannot be
634
   determined or itself is considered an interprocedural invariant.  */
635
 
636
static tree
637
ipa_get_jf_pass_through_result (struct ipa_jump_func *jfunc, tree input)
638
{
639
  tree restype, res;
640
 
641
  gcc_checking_assert (is_gimple_ip_invariant (input));
642
  if (jfunc->value.pass_through.operation == NOP_EXPR)
643
    return input;
644
 
645
  if (TREE_CODE_CLASS (jfunc->value.pass_through.operation)
646
      == tcc_comparison)
647
    restype = boolean_type_node;
648
  else
649
    restype = TREE_TYPE (input);
650
  res = fold_binary (jfunc->value.pass_through.operation, restype,
651
                     input, jfunc->value.pass_through.operand);
652
 
653
  if (res && !is_gimple_ip_invariant (res))
654
    return NULL_TREE;
655
 
656
  return res;
657
}
658
 
659
/* Return the result of an ancestor jump function JFUNC on the constant value
660
   INPUT.  Return NULL_TREE if that cannot be determined.  */
661
 
662
static tree
663
ipa_get_jf_ancestor_result (struct ipa_jump_func *jfunc, tree input)
664
{
665
  if (TREE_CODE (input) == ADDR_EXPR)
666
    {
667
      tree t = TREE_OPERAND (input, 0);
668
      t = build_ref_for_offset (EXPR_LOCATION (t), t,
669
                                jfunc->value.ancestor.offset,
670
                                jfunc->value.ancestor.type, NULL, false);
671
      return build_fold_addr_expr (t);
672
    }
673
  else
674
    return NULL_TREE;
675
}
676
 
677
/* Extract the acual BINFO being described by JFUNC which must be a known type
678
   jump function.  */
679
 
680
static tree
681
ipa_value_from_known_type_jfunc (struct ipa_jump_func *jfunc)
682
{
683
  tree base_binfo = TYPE_BINFO (jfunc->value.known_type.base_type);
684
  if (!base_binfo)
685
    return NULL_TREE;
686
  return get_binfo_at_offset (base_binfo,
687
                              jfunc->value.known_type.offset,
688
                              jfunc->value.known_type.component_type);
689
}
690
 
691
/* Determine whether JFUNC evaluates to a known value (that is either a
692
   constant or a binfo) and if so, return it.  Otherwise return NULL. INFO
693
   describes the caller node so that pass-through jump functions can be
694
   evaluated.  */
695
 
696
tree
697
ipa_value_from_jfunc (struct ipa_node_params *info, struct ipa_jump_func *jfunc)
698
{
699
  if (jfunc->type == IPA_JF_CONST)
700
    return jfunc->value.constant;
701
  else if (jfunc->type == IPA_JF_KNOWN_TYPE)
702
    return ipa_value_from_known_type_jfunc (jfunc);
703
  else if (jfunc->type == IPA_JF_PASS_THROUGH
704
           || jfunc->type == IPA_JF_ANCESTOR)
705
    {
706
      tree input;
707
      int idx;
708
 
709
      if (jfunc->type == IPA_JF_PASS_THROUGH)
710
        idx = jfunc->value.pass_through.formal_id;
711
      else
712
        idx = jfunc->value.ancestor.formal_id;
713
 
714
      if (info->ipcp_orig_node)
715
        input = VEC_index (tree, info->known_vals, idx);
716
      else
717
        {
718
          struct ipcp_lattice *lat;
719
 
720
          if (!info->lattices)
721
            {
722
              gcc_checking_assert (!flag_ipa_cp);
723
              return NULL_TREE;
724
            }
725
          lat = ipa_get_lattice (info, idx);
726
          if (!ipa_lat_is_single_const (lat))
727
            return NULL_TREE;
728
          input = lat->values->value;
729
        }
730
 
731
      if (!input)
732
        return NULL_TREE;
733
 
734
      if (jfunc->type == IPA_JF_PASS_THROUGH)
735
        {
736
          if (jfunc->value.pass_through.operation == NOP_EXPR)
737
            return input;
738
          else if (TREE_CODE (input) == TREE_BINFO)
739
            return NULL_TREE;
740
          else
741
            return ipa_get_jf_pass_through_result (jfunc, input);
742
        }
743
      else
744
        {
745
          if (TREE_CODE (input) == TREE_BINFO)
746
            return get_binfo_at_offset (input, jfunc->value.ancestor.offset,
747
                                        jfunc->value.ancestor.type);
748
          else
749
            return ipa_get_jf_ancestor_result (jfunc, input);
750
        }
751
    }
752
  else
753
    return NULL_TREE;
754
}
755
 
756
 
757
/* If checking is enabled, verify that no lattice is in the TOP state, i.e. not
758
   bottom, not containing a variable component and without any known value at
759
   the same time.  */
760
 
761
DEBUG_FUNCTION void
762
ipcp_verify_propagated_values (void)
763
{
764
  struct cgraph_node *node;
765
 
766
  FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
767
    {
768
      struct ipa_node_params *info = IPA_NODE_REF (node);
769
      int i, count = ipa_get_param_count (info);
770
 
771
      for (i = 0; i < count; i++)
772
        {
773
          struct ipcp_lattice *lat = ipa_get_lattice (info, i);
774
 
775
          if (!lat->bottom
776
              && !lat->contains_variable
777
              && lat->values_count == 0)
778
            {
779
              if (dump_file)
780
                {
781
                  fprintf (dump_file, "\nIPA lattices after constant "
782
                           "propagation:\n");
783
                  print_all_lattices (dump_file, true, false);
784
                }
785
 
786
              gcc_unreachable ();
787
            }
788
        }
789
    }
790
}
791
 
792
/* Return true iff X and Y should be considered equal values by IPA-CP.  */
793
 
794
static bool
795
values_equal_for_ipcp_p (tree x, tree y)
796
{
797
  gcc_checking_assert (x != NULL_TREE && y != NULL_TREE);
798
 
799
  if (x == y)
800
    return true;
801
 
802
  if (TREE_CODE (x) == TREE_BINFO || TREE_CODE (y) == TREE_BINFO)
803
    return false;
804
 
805
  if (TREE_CODE (x) ==  ADDR_EXPR
806
      && TREE_CODE (y) ==  ADDR_EXPR
807
      && TREE_CODE (TREE_OPERAND (x, 0)) == CONST_DECL
808
      && TREE_CODE (TREE_OPERAND (y, 0)) == CONST_DECL)
809
    return operand_equal_p (DECL_INITIAL (TREE_OPERAND (x, 0)),
810
                            DECL_INITIAL (TREE_OPERAND (y, 0)), 0);
811
  else
812
    return operand_equal_p (x, y, 0);
813
}
814
 
815
/* Add a new value source to VAL, marking that a value comes from edge CS and
816
   (if the underlying jump function is a pass-through or an ancestor one) from
817
   a caller value SRC_VAL of a caller parameter described by SRC_INDEX.  */
818
 
819
static void
820
add_value_source (struct ipcp_value *val, struct cgraph_edge *cs,
821
                  struct ipcp_value *src_val, int src_idx)
822
{
823
  struct ipcp_value_source *src;
824
 
825
  src = (struct ipcp_value_source *) pool_alloc (ipcp_sources_pool);
826
  src->cs = cs;
827
  src->val = src_val;
828
  src->index = src_idx;
829
 
830
  src->next = val->sources;
831
  val->sources = src;
832
}
833
 
834
 
835
/* Try to add NEWVAL to LAT, potentially creating a new struct ipcp_value for
836
   it.  CS, SRC_VAL and SRC_INDEX are meant for add_value_source and have the
837
   same meaning.  */
838
 
839
static bool
840
add_value_to_lattice (struct ipcp_lattice *lat, tree newval,
841
                      struct cgraph_edge *cs, struct ipcp_value *src_val,
842
                      int src_idx)
843
{
844
  struct ipcp_value *val;
845
 
846
  if (lat->bottom)
847
    return false;
848
 
849
 
850
  for (val = lat->values; val; val = val->next)
851
    if (values_equal_for_ipcp_p (val->value, newval))
852
      {
853
        if (edge_within_scc (cs))
854
          {
855
            struct ipcp_value_source *s;
856
            for (s = val->sources; s ; s = s->next)
857
              if (s->cs == cs)
858
                break;
859
            if (s)
860
              return false;
861
          }
862
 
863
        add_value_source (val, cs, src_val, src_idx);
864
        return false;
865
      }
866
 
867
  if (lat->values_count == PARAM_VALUE (PARAM_IPA_CP_VALUE_LIST_SIZE))
868
    {
869
      /* We can only free sources, not the values themselves, because sources
870
         of other values in this this SCC might point to them.   */
871
      for (val = lat->values; val; val = val->next)
872
        {
873
          while (val->sources)
874
            {
875
              struct ipcp_value_source *src = val->sources;
876
              val->sources = src->next;
877
              pool_free (ipcp_sources_pool, src);
878
            }
879
        }
880
 
881
      lat->values = NULL;
882
      return set_lattice_to_bottom (lat);
883
    }
884
 
885
  lat->values_count++;
886
  val = (struct ipcp_value *) pool_alloc (ipcp_values_pool);
887
  memset (val, 0, sizeof (*val));
888
 
889
  add_value_source (val, cs, src_val, src_idx);
890
  val->value = newval;
891
  val->next = lat->values;
892
  lat->values = val;
893
  return true;
894
}
895
 
896
/* Propagate values through a pass-through jump function JFUNC associated with
897
   edge CS, taking values from SRC_LAT and putting them into DEST_LAT.  SRC_IDX
898
   is the index of the source parameter.  */
899
 
900
static bool
901
propagate_vals_accross_pass_through (struct cgraph_edge *cs,
902
                                     struct ipa_jump_func *jfunc,
903
                                     struct ipcp_lattice *src_lat,
904
                                     struct ipcp_lattice *dest_lat,
905
                                     int src_idx)
906
{
907
  struct ipcp_value *src_val;
908
  bool ret = false;
909
 
910
  if (jfunc->value.pass_through.operation == NOP_EXPR)
911
    for (src_val = src_lat->values; src_val; src_val = src_val->next)
912
      ret |= add_value_to_lattice (dest_lat, src_val->value, cs,
913
                                   src_val, src_idx);
914
  /* Do not create new values when propagating within an SCC because if there
915
     arithmetic functions with circular dependencies, there is infinite number
916
     of them and we would just make lattices bottom.  */
917
  else if (edge_within_scc (cs))
918
    ret = set_lattice_contains_variable (dest_lat);
919
  else
920
    for (src_val = src_lat->values; src_val; src_val = src_val->next)
921
      {
922
        tree cstval = src_val->value;
923
 
924
        if (TREE_CODE (cstval) == TREE_BINFO)
925
          {
926
            ret |= set_lattice_contains_variable (dest_lat);
927
            continue;
928
          }
929
        cstval = ipa_get_jf_pass_through_result (jfunc, cstval);
930
 
931
        if (cstval)
932
          ret |= add_value_to_lattice (dest_lat, cstval, cs, src_val, src_idx);
933
        else
934
          ret |= set_lattice_contains_variable (dest_lat);
935
      }
936
 
937
  return ret;
938
}
939
 
940
/* Propagate values through an ancestor jump function JFUNC associated with
941
   edge CS, taking values from SRC_LAT and putting them into DEST_LAT.  SRC_IDX
942
   is the index of the source parameter.  */
943
 
944
static bool
945
propagate_vals_accross_ancestor (struct cgraph_edge *cs,
946
                                 struct ipa_jump_func *jfunc,
947
                                 struct ipcp_lattice *src_lat,
948
                                 struct ipcp_lattice *dest_lat,
949
                                 int src_idx)
950
{
951
  struct ipcp_value *src_val;
952
  bool ret = false;
953
 
954
  if (edge_within_scc (cs))
955
    return set_lattice_contains_variable (dest_lat);
956
 
957
  for (src_val = src_lat->values; src_val; src_val = src_val->next)
958
    {
959
      tree t = src_val->value;
960
 
961
      if (TREE_CODE (t) == TREE_BINFO)
962
        t = get_binfo_at_offset (t, jfunc->value.ancestor.offset,
963
                                 jfunc->value.ancestor.type);
964
      else
965
        t = ipa_get_jf_ancestor_result (jfunc, t);
966
 
967
      if (t)
968
        ret |= add_value_to_lattice (dest_lat, t, cs, src_val, src_idx);
969
      else
970
        ret |= set_lattice_contains_variable (dest_lat);
971
    }
972
 
973
  return ret;
974
}
975
 
976
/* Propagate values across jump function JFUNC that is associated with edge CS
977
   and put the values into DEST_LAT.  */
978
 
979
static bool
980
propagate_accross_jump_function (struct cgraph_edge *cs,
981
                                 struct ipa_jump_func *jfunc,
982
                                 struct ipcp_lattice *dest_lat)
983
{
984
  if (dest_lat->bottom)
985
    return false;
986
 
987
  if (jfunc->type == IPA_JF_CONST
988
      || jfunc->type == IPA_JF_KNOWN_TYPE)
989
    {
990
      tree val;
991
 
992
      if (jfunc->type == IPA_JF_KNOWN_TYPE)
993
        {
994
          val = ipa_value_from_known_type_jfunc (jfunc);
995
          if (!val)
996
            return set_lattice_contains_variable (dest_lat);
997
        }
998
      else
999
        val = jfunc->value.constant;
1000
      return add_value_to_lattice (dest_lat, val, cs, NULL, 0);
1001
    }
1002
  else if (jfunc->type == IPA_JF_PASS_THROUGH
1003
           || jfunc->type == IPA_JF_ANCESTOR)
1004
    {
1005
      struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1006
      struct ipcp_lattice *src_lat;
1007
      int src_idx;
1008
      bool ret;
1009
 
1010
      if (jfunc->type == IPA_JF_PASS_THROUGH)
1011
        src_idx = jfunc->value.pass_through.formal_id;
1012
      else
1013
        src_idx = jfunc->value.ancestor.formal_id;
1014
 
1015
      src_lat = ipa_get_lattice (caller_info, src_idx);
1016
      if (src_lat->bottom)
1017
        return set_lattice_contains_variable (dest_lat);
1018
 
1019
      /* If we would need to clone the caller and cannot, do not propagate.  */
1020
      if (!ipcp_versionable_function_p (cs->caller)
1021
          && (src_lat->contains_variable
1022
              || (src_lat->values_count > 1)))
1023
        return set_lattice_contains_variable (dest_lat);
1024
 
1025
      if (jfunc->type == IPA_JF_PASS_THROUGH)
1026
        ret = propagate_vals_accross_pass_through (cs, jfunc, src_lat,
1027
                                                   dest_lat, src_idx);
1028
      else
1029
        ret = propagate_vals_accross_ancestor (cs, jfunc, src_lat, dest_lat,
1030
                                               src_idx);
1031
 
1032
      if (src_lat->contains_variable)
1033
        ret |= set_lattice_contains_variable (dest_lat);
1034
 
1035
      return ret;
1036
    }
1037
 
1038
  /* TODO: We currently do not handle member method pointers in IPA-CP (we only
1039
     use it for indirect inlining), we should propagate them too.  */
1040
  return set_lattice_contains_variable (dest_lat);
1041
}
1042
 
1043
/* Propagate constants from the caller to the callee of CS.  INFO describes the
1044
   caller.  */
1045
 
1046
static bool
1047
propagate_constants_accross_call (struct cgraph_edge *cs)
1048
{
1049
  struct ipa_node_params *callee_info;
1050
  enum availability availability;
1051
  struct cgraph_node *callee, *alias_or_thunk;
1052
  struct ipa_edge_args *args;
1053
  bool ret = false;
1054
  int i, args_count, parms_count;
1055
 
1056
  callee = cgraph_function_node (cs->callee, &availability);
1057
  if (!callee->analyzed)
1058
    return false;
1059
  gcc_checking_assert (cgraph_function_with_gimple_body_p (callee));
1060
  callee_info = IPA_NODE_REF (callee);
1061
 
1062
  args = IPA_EDGE_REF (cs);
1063
  args_count = ipa_get_cs_argument_count (args);
1064
  parms_count = ipa_get_param_count (callee_info);
1065
 
1066
  /* If this call goes through a thunk we must not propagate to the first (0th)
1067
     parameter.  However, we might need to uncover a thunk from below a series
1068
     of aliases first.  */
1069
  alias_or_thunk = cs->callee;
1070
  while (alias_or_thunk->alias)
1071
    alias_or_thunk = cgraph_alias_aliased_node (alias_or_thunk);
1072
  if (alias_or_thunk->thunk.thunk_p)
1073
    {
1074
      ret |= set_lattice_contains_variable (ipa_get_lattice (callee_info, 0));
1075
      i = 1;
1076
    }
1077
  else
1078
    i = 0;
1079
 
1080
  for (; (i < args_count) && (i < parms_count); i++)
1081
    {
1082
      struct ipa_jump_func *jump_func = ipa_get_ith_jump_func (args, i);
1083
      struct ipcp_lattice *dest_lat = ipa_get_lattice (callee_info, i);
1084
 
1085
      if (availability == AVAIL_OVERWRITABLE)
1086
        ret |= set_lattice_contains_variable (dest_lat);
1087
      else
1088
        ret |= propagate_accross_jump_function (cs, jump_func, dest_lat);
1089
    }
1090
  for (; i < parms_count; i++)
1091
    ret |= set_lattice_contains_variable (ipa_get_lattice (callee_info, i));
1092
 
1093
  return ret;
1094
}
1095
 
1096
/* If an indirect edge IE can be turned into a direct one based on KNOWN_VALS
1097
   (which can contain both constants and binfos) or KNOWN_BINFOS (which can be
1098
   NULL) return the destination.  */
1099
 
1100
tree
1101
ipa_get_indirect_edge_target (struct cgraph_edge *ie,
1102
                              VEC (tree, heap) *known_vals,
1103
                              VEC (tree, heap) *known_binfos)
1104
{
1105
  int param_index = ie->indirect_info->param_index;
1106
  HOST_WIDE_INT token, anc_offset;
1107
  tree otr_type;
1108
  tree t;
1109
 
1110
  if (param_index == -1)
1111
    return NULL_TREE;
1112
 
1113
  if (!ie->indirect_info->polymorphic)
1114
    {
1115
      tree t = (VEC_length (tree, known_vals) > (unsigned int) param_index
1116
                ? VEC_index (tree, known_vals, param_index) : NULL);
1117
      if (t &&
1118
          TREE_CODE (t) == ADDR_EXPR
1119
          && TREE_CODE (TREE_OPERAND (t, 0)) == FUNCTION_DECL)
1120
        return TREE_OPERAND (t, 0);
1121
      else
1122
        return NULL_TREE;
1123
    }
1124
 
1125
  token = ie->indirect_info->otr_token;
1126
  anc_offset = ie->indirect_info->anc_offset;
1127
  otr_type = ie->indirect_info->otr_type;
1128
 
1129
  t = VEC_index (tree, known_vals, param_index);
1130
  if (!t && known_binfos
1131
      && VEC_length (tree, known_binfos) > (unsigned int) param_index)
1132
    t = VEC_index (tree, known_binfos, param_index);
1133
  if (!t)
1134
    return NULL_TREE;
1135
 
1136
  if (TREE_CODE (t) != TREE_BINFO)
1137
    {
1138
      tree binfo;
1139
      binfo = gimple_extract_devirt_binfo_from_cst (t);
1140
      if (!binfo)
1141
        return NULL_TREE;
1142
      binfo = get_binfo_at_offset (binfo, anc_offset, otr_type);
1143
      if (!binfo)
1144
        return NULL_TREE;
1145
      return gimple_get_virt_method_for_binfo (token, binfo);
1146
    }
1147
  else
1148
    {
1149
      tree binfo;
1150
 
1151
      binfo = get_binfo_at_offset (t, anc_offset, otr_type);
1152
      if (!binfo)
1153
        return NULL_TREE;
1154
      return gimple_get_virt_method_for_binfo (token, binfo);
1155
    }
1156
}
1157
 
1158
/* Calculate devirtualization time bonus for NODE, assuming we know KNOWN_CSTS
1159
   and KNOWN_BINFOS.  */
1160
 
1161
static int
1162
devirtualization_time_bonus (struct cgraph_node *node,
1163
                             VEC (tree, heap) *known_csts,
1164
                             VEC (tree, heap) *known_binfos)
1165
{
1166
  struct cgraph_edge *ie;
1167
  int res = 0;
1168
 
1169
  for (ie = node->indirect_calls; ie; ie = ie->next_callee)
1170
    {
1171
      struct cgraph_node *callee;
1172
      struct inline_summary *isummary;
1173
      tree target;
1174
 
1175
      target = ipa_get_indirect_edge_target (ie, known_csts, known_binfos);
1176
      if (!target)
1177
        continue;
1178
 
1179
      /* Only bare minimum benefit for clearly un-inlineable targets.  */
1180
      res += 1;
1181
      callee = cgraph_get_node (target);
1182
      if (!callee || !callee->analyzed)
1183
        continue;
1184
      isummary = inline_summary (callee);
1185
      if (!isummary->inlinable)
1186
        continue;
1187
 
1188
      /* FIXME: The values below need re-considering and perhaps also
1189
         integrating into the cost metrics, at lest in some very basic way.  */
1190
      if (isummary->size <= MAX_INLINE_INSNS_AUTO / 4)
1191
        res += 31;
1192
      else if (isummary->size <= MAX_INLINE_INSNS_AUTO / 2)
1193
        res += 15;
1194
      else if (isummary->size <= MAX_INLINE_INSNS_AUTO
1195
               || DECL_DECLARED_INLINE_P (callee->decl))
1196
        res += 7;
1197
    }
1198
 
1199
  return res;
1200
}
1201
 
1202
/* Return true if cloning NODE is a good idea, given the estimated TIME_BENEFIT
1203
   and SIZE_COST and with the sum of frequencies of incoming edges to the
1204
   potential new clone in FREQUENCIES.  */
1205
 
1206
static bool
1207
good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit,
1208
                            int freq_sum, gcov_type count_sum, int size_cost)
1209
{
1210
  if (time_benefit == 0
1211
      || !flag_ipa_cp_clone
1212
      || !optimize_function_for_speed_p (DECL_STRUCT_FUNCTION (node->decl)))
1213
    return false;
1214
 
1215
  gcc_assert (size_cost > 0);
1216
 
1217
  if (max_count)
1218
    {
1219
      int factor = (count_sum * 1000) / max_count;
1220
      HOST_WIDEST_INT evaluation = (((HOST_WIDEST_INT) time_benefit * factor)
1221
                                    / size_cost);
1222
 
1223
      if (dump_file && (dump_flags & TDF_DETAILS))
1224
        fprintf (dump_file, "     good_cloning_opportunity_p (time: %i, "
1225
                 "size: %i, count_sum: " HOST_WIDE_INT_PRINT_DEC
1226
                 ") -> evaluation: " HOST_WIDEST_INT_PRINT_DEC
1227
                 ", threshold: %i\n",
1228
                 time_benefit, size_cost, (HOST_WIDE_INT) count_sum,
1229
                 evaluation, 500);
1230
 
1231
      return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
1232
    }
1233
  else
1234
    {
1235
      HOST_WIDEST_INT evaluation = (((HOST_WIDEST_INT) time_benefit * freq_sum)
1236
                                    / size_cost);
1237
 
1238
      if (dump_file && (dump_flags & TDF_DETAILS))
1239
        fprintf (dump_file, "     good_cloning_opportunity_p (time: %i, "
1240
                 "size: %i, freq_sum: %i) -> evaluation: "
1241
                 HOST_WIDEST_INT_PRINT_DEC ", threshold: %i\n",
1242
                 time_benefit, size_cost, freq_sum, evaluation,
1243
                 CGRAPH_FREQ_BASE /2);
1244
 
1245
      return evaluation >= PARAM_VALUE (PARAM_IPA_CP_EVAL_THRESHOLD);
1246
    }
1247
}
1248
 
1249
 
1250
/* Allocate KNOWN_CSTS and KNOWN_BINFOS and populate them with values of
1251
   parameters that are known independent of the context.  INFO describes the
1252
   function.  If REMOVABLE_PARAMS_COST is non-NULL, the movement cost of all
1253
   removable parameters will be stored in it.  */
1254
 
1255
static bool
1256
gather_context_independent_values (struct ipa_node_params *info,
1257
                                   VEC (tree, heap) **known_csts,
1258
                                   VEC (tree, heap) **known_binfos,
1259
                                   int *removable_params_cost)
1260
{
1261
  int i, count = ipa_get_param_count (info);
1262
  bool ret = false;
1263
 
1264
  *known_csts = NULL;
1265
  *known_binfos = NULL;
1266
  VEC_safe_grow_cleared (tree, heap, *known_csts, count);
1267
  VEC_safe_grow_cleared (tree, heap, *known_binfos, count);
1268
 
1269
  if (removable_params_cost)
1270
    *removable_params_cost = 0;
1271
 
1272
  for (i = 0; i < count ; i++)
1273
    {
1274
      struct ipcp_lattice *lat = ipa_get_lattice (info, i);
1275
 
1276
      if (ipa_lat_is_single_const (lat))
1277
        {
1278
          struct ipcp_value *val = lat->values;
1279
          if (TREE_CODE (val->value) != TREE_BINFO)
1280
            {
1281
              VEC_replace (tree, *known_csts, i, val->value);
1282
              if (removable_params_cost)
1283
                *removable_params_cost
1284
                  += estimate_move_cost (TREE_TYPE (val->value));
1285
              ret = true;
1286
            }
1287
          else if (lat->virt_call)
1288
            {
1289
              VEC_replace (tree, *known_binfos, i, val->value);
1290
              ret = true;
1291
            }
1292
          else if (removable_params_cost
1293
                   && !ipa_is_param_used (info, i))
1294
            *removable_params_cost
1295
              += estimate_move_cost (TREE_TYPE (ipa_get_param (info, i)));
1296
        }
1297
      else if (removable_params_cost
1298
               && !ipa_is_param_used (info, i))
1299
        *removable_params_cost
1300
          +=  estimate_move_cost (TREE_TYPE (ipa_get_param (info, i)));
1301
    }
1302
 
1303
  return ret;
1304
}
1305
 
1306
/* Iterate over known values of parameters of NODE and estimate the local
1307
   effects in terms of time and size they have.  */
1308
 
1309
static void
1310
estimate_local_effects (struct cgraph_node *node)
1311
{
1312
  struct ipa_node_params *info = IPA_NODE_REF (node);
1313
  int i, count = ipa_get_param_count (info);
1314
  VEC (tree, heap) *known_csts, *known_binfos;
1315
  bool always_const;
1316
  int base_time = inline_summary (node)->time;
1317
  int removable_params_cost;
1318
 
1319
  if (!count || !ipcp_versionable_function_p (node))
1320
    return;
1321
 
1322
  if (dump_file && (dump_flags & TDF_DETAILS))
1323
    fprintf (dump_file, "\nEstimating effects for %s/%i, base_time: %i.\n",
1324
             cgraph_node_name (node), node->uid, base_time);
1325
 
1326
  always_const = gather_context_independent_values (info, &known_csts,
1327
                                                    &known_binfos,
1328
                                                    &removable_params_cost);
1329
  if (always_const)
1330
    {
1331
      struct caller_statistics stats;
1332
      int time, size;
1333
 
1334
      init_caller_stats (&stats);
1335
      cgraph_for_node_and_aliases (node, gather_caller_stats, &stats, false);
1336
      estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos,
1337
                                         &size, &time);
1338
      time -= devirtualization_time_bonus (node, known_csts, known_binfos);
1339
      time -= removable_params_cost;
1340
      size -= stats.n_calls * removable_params_cost;
1341
 
1342
      if (dump_file)
1343
        fprintf (dump_file, " - context independent values, size: %i, "
1344
                 "time_benefit: %i\n", size, base_time - time);
1345
 
1346
      if (size <= 0
1347
          || cgraph_will_be_removed_from_program_if_no_direct_calls (node))
1348
        {
1349
          info->clone_for_all_contexts = true;
1350
          base_time = time;
1351
 
1352
          if (dump_file)
1353
            fprintf (dump_file, "     Decided to specialize for all "
1354
                     "known contexts, code not going to grow.\n");
1355
        }
1356
      else if (good_cloning_opportunity_p (node, base_time - time,
1357
                                           stats.freq_sum, stats.count_sum,
1358
                                           size))
1359
        {
1360
          if (size + overall_size <= max_new_size)
1361
            {
1362
              info->clone_for_all_contexts = true;
1363
              base_time = time;
1364
              overall_size += size;
1365
 
1366
              if (dump_file)
1367
                fprintf (dump_file, "     Decided to specialize for all "
1368
                         "known contexts, growth deemed beneficial.\n");
1369
            }
1370
          else if (dump_file && (dump_flags & TDF_DETAILS))
1371
            fprintf (dump_file, "   Not cloning for all contexts because "
1372
                     "max_new_size would be reached with %li.\n",
1373
                     size + overall_size);
1374
        }
1375
    }
1376
 
1377
  for (i = 0; i < count ; i++)
1378
    {
1379
      struct ipcp_lattice *lat = ipa_get_lattice (info, i);
1380
      struct ipcp_value *val;
1381
      int emc;
1382
 
1383
      if (lat->bottom
1384
          || !lat->values
1385
          || VEC_index (tree, known_csts, i)
1386
          || VEC_index (tree, known_binfos, i))
1387
        continue;
1388
 
1389
      for (val = lat->values; val; val = val->next)
1390
        {
1391
          int time, size, time_benefit;
1392
 
1393
          if (TREE_CODE (val->value) != TREE_BINFO)
1394
            {
1395
              VEC_replace (tree, known_csts, i, val->value);
1396
              VEC_replace (tree, known_binfos, i, NULL_TREE);
1397
              emc = estimate_move_cost (TREE_TYPE (val->value));
1398
            }
1399
          else if (lat->virt_call)
1400
            {
1401
              VEC_replace (tree, known_csts, i, NULL_TREE);
1402
              VEC_replace (tree, known_binfos, i, val->value);
1403
              emc = 0;
1404
            }
1405
          else
1406
            continue;
1407
 
1408
          estimate_ipcp_clone_size_and_time (node, known_csts, known_binfos,
1409
                                             &size, &time);
1410
          time_benefit = base_time - time
1411
            + devirtualization_time_bonus (node, known_csts, known_binfos)
1412
            + removable_params_cost + emc;
1413
 
1414
          gcc_checking_assert (size >=0);
1415
          /* The inliner-heuristics based estimates may think that in certain
1416
             contexts some functions do not have any size at all but we want
1417
             all specializations to have at least a tiny cost, not least not to
1418
             divide by zero.  */
1419
          if (size == 0)
1420
            size = 1;
1421
 
1422
          if (dump_file && (dump_flags & TDF_DETAILS))
1423
            {
1424
              fprintf (dump_file, " - estimates for value ");
1425
              print_ipcp_constant_value (dump_file, val->value);
1426
              fprintf (dump_file, " for parameter ");
1427
              print_generic_expr (dump_file, ipa_get_param (info, i), 0);
1428
              fprintf (dump_file, ": time_benefit: %i, size: %i\n",
1429
                       time_benefit, size);
1430
            }
1431
 
1432
          val->local_time_benefit = time_benefit;
1433
          val->local_size_cost = size;
1434
        }
1435
    }
1436
 
1437
  VEC_free (tree, heap, known_csts);
1438
  VEC_free (tree, heap, known_binfos);
1439
}
1440
 
1441
 
1442
/* Add value CUR_VAL and all yet-unsorted values it is dependent on to the
1443
   topological sort of values.  */
1444
 
1445
static void
1446
add_val_to_toposort (struct ipcp_value *cur_val)
1447
{
1448
  static int dfs_counter = 0;
1449
  static struct ipcp_value *stack;
1450
  struct ipcp_value_source *src;
1451
 
1452
  if (cur_val->dfs)
1453
    return;
1454
 
1455
  dfs_counter++;
1456
  cur_val->dfs = dfs_counter;
1457
  cur_val->low_link = dfs_counter;
1458
 
1459
  cur_val->topo_next = stack;
1460
  stack = cur_val;
1461
  cur_val->on_stack = true;
1462
 
1463
  for (src = cur_val->sources; src; src = src->next)
1464
    if (src->val)
1465
      {
1466
        if (src->val->dfs == 0)
1467
          {
1468
            add_val_to_toposort (src->val);
1469
            if (src->val->low_link < cur_val->low_link)
1470
              cur_val->low_link = src->val->low_link;
1471
          }
1472
        else if (src->val->on_stack
1473
                 && src->val->dfs < cur_val->low_link)
1474
          cur_val->low_link = src->val->dfs;
1475
      }
1476
 
1477
  if (cur_val->dfs == cur_val->low_link)
1478
    {
1479
      struct ipcp_value *v, *scc_list = NULL;
1480
 
1481
      do
1482
        {
1483
          v = stack;
1484
          stack = v->topo_next;
1485
          v->on_stack = false;
1486
 
1487
          v->scc_next = scc_list;
1488
          scc_list = v;
1489
        }
1490
      while (v != cur_val);
1491
 
1492
      cur_val->topo_next = values_topo;
1493
      values_topo = cur_val;
1494
    }
1495
}
1496
 
1497
/* Add all values in lattices associated with NODE to the topological sort if
1498
   they are not there yet.  */
1499
 
1500
static void
1501
add_all_node_vals_to_toposort (struct cgraph_node *node)
1502
{
1503
  struct ipa_node_params *info = IPA_NODE_REF (node);
1504
  int i, count = ipa_get_param_count (info);
1505
 
1506
  for (i = 0; i < count ; i++)
1507
    {
1508
      struct ipcp_lattice *lat = ipa_get_lattice (info, i);
1509
      struct ipcp_value *val;
1510
 
1511
      if (lat->bottom || !lat->values)
1512
        continue;
1513
      for (val = lat->values; val; val = val->next)
1514
        add_val_to_toposort (val);
1515
    }
1516
}
1517
 
1518
/* One pass of constants propagation along the call graph edges, from callers
1519
   to callees (requires topological ordering in TOPO), iterate over strongly
1520
   connected components.  */
1521
 
1522
static void
1523
propagate_constants_topo (struct topo_info *topo)
1524
{
1525
  int i;
1526
 
1527
  for (i = topo->nnodes - 1; i >= 0; i--)
1528
    {
1529
      struct cgraph_node *v, *node = topo->order[i];
1530
      struct ipa_dfs_info *node_dfs_info;
1531
 
1532
      if (!cgraph_function_with_gimple_body_p (node))
1533
        continue;
1534
 
1535
      node_dfs_info = (struct ipa_dfs_info *) node->aux;
1536
      /* First, iteratively propagate within the strongly connected component
1537
         until all lattices stabilize.  */
1538
      v = node_dfs_info->next_cycle;
1539
      while (v)
1540
        {
1541
          push_node_to_stack (topo, v);
1542
          v = ((struct ipa_dfs_info *) v->aux)->next_cycle;
1543
        }
1544
 
1545
      v = node;
1546
      while (v)
1547
        {
1548
          struct cgraph_edge *cs;
1549
 
1550
          for (cs = v->callees; cs; cs = cs->next_callee)
1551
            if (edge_within_scc (cs)
1552
                && propagate_constants_accross_call (cs))
1553
              push_node_to_stack (topo, cs->callee);
1554
          v = pop_node_from_stack (topo);
1555
        }
1556
 
1557
      /* Afterwards, propagate along edges leading out of the SCC, calculates
1558
         the local effects of the discovered constants and all valid values to
1559
         their topological sort.  */
1560
      v = node;
1561
      while (v)
1562
        {
1563
          struct cgraph_edge *cs;
1564
 
1565
          estimate_local_effects (v);
1566
          add_all_node_vals_to_toposort (v);
1567
          for (cs = v->callees; cs; cs = cs->next_callee)
1568
            if (!edge_within_scc (cs))
1569
              propagate_constants_accross_call (cs);
1570
 
1571
          v = ((struct ipa_dfs_info *) v->aux)->next_cycle;
1572
        }
1573
    }
1574
}
1575
 
1576
 
1577
/* Return the sum of A and B if none of them is bigger than INT_MAX/2, return
1578
   the bigger one if otherwise.  */
1579
 
1580
static int
1581
safe_add (int a, int b)
1582
{
1583
  if (a > INT_MAX/2 || b > INT_MAX/2)
1584
    return a > b ? a : b;
1585
  else
1586
    return a + b;
1587
}
1588
 
1589
 
1590
/* Propagate the estimated effects of individual values along the topological
1591
   from the dependant values to those they depend on.  */
1592
 
1593
static void
1594
propagate_effects (void)
1595
{
1596
  struct ipcp_value *base;
1597
 
1598
  for (base = values_topo; base; base = base->topo_next)
1599
    {
1600
      struct ipcp_value_source *src;
1601
      struct ipcp_value *val;
1602
      int time = 0, size = 0;
1603
 
1604
      for (val = base; val; val = val->scc_next)
1605
        {
1606
          time = safe_add (time,
1607
                           val->local_time_benefit + val->prop_time_benefit);
1608
          size = safe_add (size, val->local_size_cost + val->prop_size_cost);
1609
        }
1610
 
1611
      for (val = base; val; val = val->scc_next)
1612
        for (src = val->sources; src; src = src->next)
1613
          if (src->val
1614
              && cgraph_maybe_hot_edge_p (src->cs))
1615
            {
1616
              src->val->prop_time_benefit = safe_add (time,
1617
                                                src->val->prop_time_benefit);
1618
              src->val->prop_size_cost = safe_add (size,
1619
                                                   src->val->prop_size_cost);
1620
            }
1621
    }
1622
}
1623
 
1624
 
1625
/* Propagate constants, binfos and their effects from the summaries
1626
   interprocedurally.  */
1627
 
1628
static void
1629
ipcp_propagate_stage (struct topo_info *topo)
1630
{
1631
  struct cgraph_node *node;
1632
 
1633
  if (dump_file)
1634
    fprintf (dump_file, "\n Propagating constants:\n\n");
1635
 
1636
  if (in_lto_p)
1637
    ipa_update_after_lto_read ();
1638
 
1639
 
1640
  FOR_EACH_DEFINED_FUNCTION (node)
1641
  {
1642
    struct ipa_node_params *info = IPA_NODE_REF (node);
1643
 
1644
    determine_versionability (node);
1645
    if (cgraph_function_with_gimple_body_p (node))
1646
      {
1647
        info->lattices = XCNEWVEC (struct ipcp_lattice,
1648
                                   ipa_get_param_count (info));
1649
        initialize_node_lattices (node);
1650
      }
1651
    if (node->count > max_count)
1652
      max_count = node->count;
1653
    overall_size += inline_summary (node)->self_size;
1654
  }
1655
 
1656
  max_new_size = overall_size;
1657
  if (max_new_size < PARAM_VALUE (PARAM_LARGE_UNIT_INSNS))
1658
    max_new_size = PARAM_VALUE (PARAM_LARGE_UNIT_INSNS);
1659
  max_new_size += max_new_size * PARAM_VALUE (PARAM_IPCP_UNIT_GROWTH) / 100 + 1;
1660
 
1661
  if (dump_file)
1662
    fprintf (dump_file, "\noverall_size: %li, max_new_size: %li\n",
1663
             overall_size, max_new_size);
1664
 
1665
  propagate_constants_topo (topo);
1666
#ifdef ENABLE_CHECKING
1667
  ipcp_verify_propagated_values ();
1668
#endif
1669
  propagate_effects ();
1670
 
1671
  if (dump_file)
1672
    {
1673
      fprintf (dump_file, "\nIPA lattices after all propagation:\n");
1674
      print_all_lattices (dump_file, (dump_flags & TDF_DETAILS), true);
1675
    }
1676
}
1677
 
1678
/* Discover newly direct outgoing edges from NODE which is a new clone with
1679
   known KNOWN_VALS and make them direct.  */
1680
 
1681
static void
1682
ipcp_discover_new_direct_edges (struct cgraph_node *node,
1683
                                VEC (tree, heap) *known_vals)
1684
{
1685
  struct cgraph_edge *ie, *next_ie;
1686
 
1687
  for (ie = node->indirect_calls; ie; ie = next_ie)
1688
    {
1689
      tree target;
1690
 
1691
      next_ie = ie->next_callee;
1692
      target = ipa_get_indirect_edge_target (ie, known_vals, NULL);
1693
      if (target)
1694
        ipa_make_edge_direct_to_target (ie, target);
1695
    }
1696
}
1697
 
1698
/* Vector of pointers which for linked lists of clones of an original crgaph
1699
   edge. */
1700
 
1701
static VEC (cgraph_edge_p, heap) *next_edge_clone;
1702
 
1703
static inline void
1704
grow_next_edge_clone_vector (void)
1705
{
1706
  if (VEC_length (cgraph_edge_p, next_edge_clone)
1707
      <=  (unsigned) cgraph_edge_max_uid)
1708
    VEC_safe_grow_cleared (cgraph_edge_p, heap, next_edge_clone,
1709
                           cgraph_edge_max_uid + 1);
1710
}
1711
 
1712
/* Edge duplication hook to grow the appropriate linked list in
1713
   next_edge_clone. */
1714
 
1715
static void
1716
ipcp_edge_duplication_hook (struct cgraph_edge *src, struct cgraph_edge *dst,
1717
                            __attribute__((unused)) void *data)
1718
{
1719
  grow_next_edge_clone_vector ();
1720
  VEC_replace (cgraph_edge_p, next_edge_clone, dst->uid,
1721
               VEC_index (cgraph_edge_p, next_edge_clone, src->uid));
1722
  VEC_replace (cgraph_edge_p, next_edge_clone, src->uid, dst);
1723
}
1724
 
1725
/* Get the next clone in the linked list of clones of an edge.  */
1726
 
1727
static inline struct cgraph_edge *
1728
get_next_cgraph_edge_clone (struct cgraph_edge *cs)
1729
{
1730
  return VEC_index (cgraph_edge_p, next_edge_clone, cs->uid);
1731
}
1732
 
1733
/* Return true if edge CS does bring about the value described by SRC.  */
1734
 
1735
static bool
1736
cgraph_edge_brings_value_p (struct cgraph_edge *cs,
1737
                            struct ipcp_value_source *src)
1738
{
1739
  struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
1740
 
1741
  if (IPA_NODE_REF (cs->callee)->ipcp_orig_node
1742
      || caller_info->node_dead)
1743
    return false;
1744
  if (!src->val)
1745
    return true;
1746
 
1747
  if (caller_info->ipcp_orig_node)
1748
    {
1749
      tree t = VEC_index (tree, caller_info->known_vals, src->index);
1750
      return (t != NULL_TREE
1751
              && values_equal_for_ipcp_p (src->val->value, t));
1752
    }
1753
  else
1754
    {
1755
      struct ipcp_lattice *lat = ipa_get_lattice (caller_info, src->index);
1756
      if (ipa_lat_is_single_const (lat)
1757
          && values_equal_for_ipcp_p (src->val->value, lat->values->value))
1758
        return true;
1759
      else
1760
        return false;
1761
    }
1762
}
1763
 
1764
/* Given VAL, iterate over all its sources and if they still hold, add their
1765
   edge frequency and their number into *FREQUENCY and *CALLER_COUNT
1766
   respectively.  */
1767
 
1768
static bool
1769
get_info_about_necessary_edges (struct ipcp_value *val, int *freq_sum,
1770
                                gcov_type *count_sum, int *caller_count)
1771
{
1772
  struct ipcp_value_source *src;
1773
  int freq = 0, count = 0;
1774
  gcov_type cnt = 0;
1775
  bool hot = false;
1776
 
1777
  for (src = val->sources; src; src = src->next)
1778
    {
1779
      struct cgraph_edge *cs = src->cs;
1780
      while (cs)
1781
        {
1782
          if (cgraph_edge_brings_value_p (cs, src))
1783
            {
1784
              count++;
1785
              freq += cs->frequency;
1786
              cnt += cs->count;
1787
              hot |= cgraph_maybe_hot_edge_p (cs);
1788
            }
1789
          cs = get_next_cgraph_edge_clone (cs);
1790
        }
1791
    }
1792
 
1793
  *freq_sum = freq;
1794
  *count_sum = cnt;
1795
  *caller_count = count;
1796
  return hot;
1797
}
1798
 
1799
/* Return a vector of incoming edges that do bring value VAL.  It is assumed
1800
   their number is known and equal to CALLER_COUNT.  */
1801
 
1802
static VEC (cgraph_edge_p,heap) *
1803
gather_edges_for_value (struct ipcp_value *val, int caller_count)
1804
{
1805
  struct ipcp_value_source *src;
1806
  VEC (cgraph_edge_p,heap) *ret;
1807
 
1808
  ret = VEC_alloc (cgraph_edge_p, heap, caller_count);
1809
  for (src = val->sources; src; src = src->next)
1810
    {
1811
      struct cgraph_edge *cs = src->cs;
1812
      while (cs)
1813
        {
1814
          if (cgraph_edge_brings_value_p (cs, src))
1815
            VEC_quick_push (cgraph_edge_p, ret, cs);
1816
          cs = get_next_cgraph_edge_clone (cs);
1817
        }
1818
    }
1819
 
1820
  return ret;
1821
}
1822
 
1823
/* Construct a replacement map for a know VALUE for a formal parameter PARAM.
1824
   Return it or NULL if for some reason it cannot be created.  */
1825
 
1826
static struct ipa_replace_map *
1827
get_replacement_map (tree value, tree parm)
1828
{
1829
  tree req_type = TREE_TYPE (parm);
1830
  struct ipa_replace_map *replace_map;
1831
 
1832
  if (!useless_type_conversion_p (req_type, TREE_TYPE (value)))
1833
    {
1834
      if (fold_convertible_p (req_type, value))
1835
        value = fold_build1 (NOP_EXPR, req_type, value);
1836
      else if (TYPE_SIZE (req_type) == TYPE_SIZE (TREE_TYPE (value)))
1837
        value = fold_build1 (VIEW_CONVERT_EXPR, req_type, value);
1838
      else
1839
        {
1840
          if (dump_file)
1841
            {
1842
              fprintf (dump_file, "    const ");
1843
              print_generic_expr (dump_file, value, 0);
1844
              fprintf (dump_file, "  can't be converted to param ");
1845
              print_generic_expr (dump_file, parm, 0);
1846
              fprintf (dump_file, "\n");
1847
            }
1848
          return NULL;
1849
        }
1850
    }
1851
 
1852
  replace_map = ggc_alloc_ipa_replace_map ();
1853
  if (dump_file)
1854
    {
1855
      fprintf (dump_file, "    replacing param ");
1856
      print_generic_expr (dump_file, parm, 0);
1857
      fprintf (dump_file, " with const ");
1858
      print_generic_expr (dump_file, value, 0);
1859
      fprintf (dump_file, "\n");
1860
    }
1861
  replace_map->old_tree = parm;
1862
  replace_map->new_tree = value;
1863
  replace_map->replace_p = true;
1864
  replace_map->ref_p = false;
1865
 
1866
  return replace_map;
1867
}
1868
 
1869
/* Dump new profiling counts */
1870
 
1871
static void
1872
dump_profile_updates (struct cgraph_node *orig_node,
1873
                      struct cgraph_node *new_node)
1874
{
1875
  struct cgraph_edge *cs;
1876
 
1877
  fprintf (dump_file, "    setting count of the specialized node to "
1878
           HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) new_node->count);
1879
  for (cs = new_node->callees; cs ; cs = cs->next_callee)
1880
    fprintf (dump_file, "      edge to %s has count "
1881
             HOST_WIDE_INT_PRINT_DEC "\n",
1882
             cgraph_node_name (cs->callee), (HOST_WIDE_INT) cs->count);
1883
 
1884
  fprintf (dump_file, "    setting count of the original node to "
1885
           HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) orig_node->count);
1886
  for (cs = orig_node->callees; cs ; cs = cs->next_callee)
1887
    fprintf (dump_file, "      edge to %s is left with "
1888
             HOST_WIDE_INT_PRINT_DEC "\n",
1889
             cgraph_node_name (cs->callee), (HOST_WIDE_INT) cs->count);
1890
}
1891
 
1892
/* After a specialized NEW_NODE version of ORIG_NODE has been created, update
1893
   their profile information to reflect this.  */
1894
 
1895
static void
1896
update_profiling_info (struct cgraph_node *orig_node,
1897
                       struct cgraph_node *new_node)
1898
{
1899
  struct cgraph_edge *cs;
1900
  struct caller_statistics stats;
1901
  gcov_type new_sum, orig_sum;
1902
  gcov_type remainder, orig_node_count = orig_node->count;
1903
 
1904
  if (orig_node_count == 0)
1905
    return;
1906
 
1907
  init_caller_stats (&stats);
1908
  cgraph_for_node_and_aliases (orig_node, gather_caller_stats, &stats, false);
1909
  orig_sum = stats.count_sum;
1910
  init_caller_stats (&stats);
1911
  cgraph_for_node_and_aliases (new_node, gather_caller_stats, &stats, false);
1912
  new_sum = stats.count_sum;
1913
 
1914
  if (orig_node_count < orig_sum + new_sum)
1915
    {
1916
      if (dump_file)
1917
        fprintf (dump_file, "    Problem: node %s/%i has too low count "
1918
                 HOST_WIDE_INT_PRINT_DEC " while the sum of incoming "
1919
                 "counts is " HOST_WIDE_INT_PRINT_DEC "\n",
1920
                 cgraph_node_name (orig_node), orig_node->uid,
1921
                 (HOST_WIDE_INT) orig_node_count,
1922
                 (HOST_WIDE_INT) (orig_sum + new_sum));
1923
 
1924
      orig_node_count = (orig_sum + new_sum) * 12 / 10;
1925
      if (dump_file)
1926
        fprintf (dump_file, "      proceeding by pretending it was "
1927
                 HOST_WIDE_INT_PRINT_DEC "\n",
1928
                 (HOST_WIDE_INT) orig_node_count);
1929
    }
1930
 
1931
  new_node->count = new_sum;
1932
  remainder = orig_node_count - new_sum;
1933
  orig_node->count = remainder;
1934
 
1935
  for (cs = new_node->callees; cs ; cs = cs->next_callee)
1936
    if (cs->frequency)
1937
      cs->count = cs->count * (new_sum * REG_BR_PROB_BASE
1938
                               / orig_node_count) / REG_BR_PROB_BASE;
1939
    else
1940
      cs->count = 0;
1941
 
1942
  for (cs = orig_node->callees; cs ; cs = cs->next_callee)
1943
    cs->count = cs->count * (remainder * REG_BR_PROB_BASE
1944
                             / orig_node_count) / REG_BR_PROB_BASE;
1945
 
1946
  if (dump_file)
1947
    dump_profile_updates (orig_node, new_node);
1948
}
1949
 
1950
/* Update the respective profile of specialized NEW_NODE and the original
1951
   ORIG_NODE after additional edges with cumulative count sum REDIRECTED_SUM
1952
   have been redirected to the specialized version.  */
1953
 
1954
static void
1955
update_specialized_profile (struct cgraph_node *new_node,
1956
                            struct cgraph_node *orig_node,
1957
                            gcov_type redirected_sum)
1958
{
1959
  struct cgraph_edge *cs;
1960
  gcov_type new_node_count, orig_node_count = orig_node->count;
1961
 
1962
  if (dump_file)
1963
    fprintf (dump_file, "    the sum of counts of redirected  edges is "
1964
             HOST_WIDE_INT_PRINT_DEC "\n", (HOST_WIDE_INT) redirected_sum);
1965
  if (orig_node_count == 0)
1966
    return;
1967
 
1968
  gcc_assert (orig_node_count >= redirected_sum);
1969
 
1970
  new_node_count = new_node->count;
1971
  new_node->count += redirected_sum;
1972
  orig_node->count -= redirected_sum;
1973
 
1974
  for (cs = new_node->callees; cs ; cs = cs->next_callee)
1975
    if (cs->frequency)
1976
      cs->count += cs->count * redirected_sum / new_node_count;
1977
    else
1978
      cs->count = 0;
1979
 
1980
  for (cs = orig_node->callees; cs ; cs = cs->next_callee)
1981
    {
1982
      gcov_type dec = cs->count * (redirected_sum * REG_BR_PROB_BASE
1983
                                   / orig_node_count) / REG_BR_PROB_BASE;
1984
      if (dec < cs->count)
1985
        cs->count -= dec;
1986
      else
1987
        cs->count = 0;
1988
    }
1989
 
1990
  if (dump_file)
1991
    dump_profile_updates (orig_node, new_node);
1992
}
1993
 
1994
/* Create a specialized version of NODE with known constants and types of
1995
   parameters in KNOWN_VALS and redirect all edges in CALLERS to it.  */
1996
 
1997
static struct cgraph_node *
1998
create_specialized_node (struct cgraph_node *node,
1999
                         VEC (tree, heap) *known_vals,
2000
                         VEC (cgraph_edge_p,heap) *callers)
2001
{
2002
  struct ipa_node_params *new_info, *info = IPA_NODE_REF (node);
2003
  VEC (ipa_replace_map_p,gc)* replace_trees = NULL;
2004
  struct cgraph_node *new_node;
2005
  int i, count = ipa_get_param_count (info);
2006
  bitmap args_to_skip;
2007
 
2008
  gcc_assert (!info->ipcp_orig_node);
2009
 
2010
  if (node->local.can_change_signature)
2011
    {
2012
      args_to_skip = BITMAP_GGC_ALLOC ();
2013
      for (i = 0; i < count; i++)
2014
        {
2015
          tree t = VEC_index (tree, known_vals, i);
2016
 
2017
          if ((t && TREE_CODE (t) != TREE_BINFO)
2018
              || !ipa_is_param_used (info, i))
2019
            bitmap_set_bit (args_to_skip, i);
2020
        }
2021
    }
2022
  else
2023
    {
2024
      args_to_skip = NULL;
2025
      if (dump_file && (dump_flags & TDF_DETAILS))
2026
        fprintf (dump_file, "      cannot change function signature\n");
2027
    }
2028
 
2029
  for (i = 0; i < count ; i++)
2030
    {
2031
      tree t = VEC_index (tree, known_vals, i);
2032
      if (t && TREE_CODE (t) != TREE_BINFO)
2033
        {
2034
          struct ipa_replace_map *replace_map;
2035
 
2036
          replace_map = get_replacement_map (t, ipa_get_param (info, i));
2037
          if (replace_map)
2038
            VEC_safe_push (ipa_replace_map_p, gc, replace_trees, replace_map);
2039
        }
2040
    }
2041
 
2042
  new_node = cgraph_create_virtual_clone (node, callers, replace_trees,
2043
                                          args_to_skip, "constprop");
2044
  if (dump_file && (dump_flags & TDF_DETAILS))
2045
    fprintf (dump_file, "     the new node is %s/%i.\n",
2046
             cgraph_node_name (new_node), new_node->uid);
2047
  gcc_checking_assert (ipa_node_params_vector
2048
                       && (VEC_length (ipa_node_params_t,
2049
                                       ipa_node_params_vector)
2050
                           > (unsigned) cgraph_max_uid));
2051
  update_profiling_info (node, new_node);
2052
  new_info = IPA_NODE_REF (new_node);
2053
  new_info->ipcp_orig_node = node;
2054
  new_info->known_vals = known_vals;
2055
 
2056
  ipcp_discover_new_direct_edges (new_node, known_vals);
2057
 
2058
  VEC_free (cgraph_edge_p, heap, callers);
2059
  return new_node;
2060
}
2061
 
2062
/* Given a NODE, and a subset of its CALLERS, try to populate blanks slots in
2063
   KNOWN_VALS with constants and types that are also known for all of the
2064
   CALLERS.  */
2065
 
2066
static void
2067
find_more_values_for_callers_subset (struct cgraph_node *node,
2068
                                     VEC (tree, heap) *known_vals,
2069
                                     VEC (cgraph_edge_p,heap) *callers)
2070
{
2071
  struct ipa_node_params *info = IPA_NODE_REF (node);
2072
  int i, count = ipa_get_param_count (info);
2073
 
2074
  for (i = 0; i < count ; i++)
2075
    {
2076
      struct cgraph_edge *cs;
2077
      tree newval = NULL_TREE;
2078
      int j;
2079
 
2080
      if (ipa_get_lattice (info, i)->bottom
2081
          || VEC_index (tree, known_vals, i))
2082
        continue;
2083
 
2084
      FOR_EACH_VEC_ELT (cgraph_edge_p, callers, j, cs)
2085
        {
2086
          struct ipa_jump_func *jump_func;
2087
          tree t;
2088
 
2089
          if (i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs)))
2090
            {
2091
              newval = NULL_TREE;
2092
              break;
2093
            }
2094
          jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
2095
          t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func);
2096
          if (!t
2097
              || (newval
2098
                  && !values_equal_for_ipcp_p (t, newval)))
2099
            {
2100
              newval = NULL_TREE;
2101
              break;
2102
            }
2103
          else
2104
            newval = t;
2105
        }
2106
 
2107
      if (newval)
2108
        {
2109
          if (dump_file && (dump_flags & TDF_DETAILS))
2110
            {
2111
              fprintf (dump_file, "    adding an extra known value ");
2112
              print_ipcp_constant_value (dump_file, newval);
2113
              fprintf (dump_file, " for parameter ");
2114
              print_generic_expr (dump_file, ipa_get_param (info, i), 0);
2115
              fprintf (dump_file, "\n");
2116
            }
2117
 
2118
          VEC_replace (tree, known_vals, i, newval);
2119
        }
2120
    }
2121
}
2122
 
2123
/* Given an original NODE and a VAL for which we have already created a
2124
   specialized clone, look whether there are incoming edges that still lead
2125
   into the old node but now also bring the requested value and also conform to
2126
   all other criteria such that they can be redirected the the special node.
2127
   This function can therefore redirect the final edge in a SCC.  */
2128
 
2129
static void
2130
perhaps_add_new_callers (struct cgraph_node *node, struct ipcp_value *val)
2131
{
2132
  struct ipa_node_params *dest_info = IPA_NODE_REF (val->spec_node);
2133
  struct ipcp_value_source *src;
2134
  int count = ipa_get_param_count (dest_info);
2135
  gcov_type redirected_sum = 0;
2136
 
2137
  for (src = val->sources; src; src = src->next)
2138
    {
2139
      struct cgraph_edge *cs = src->cs;
2140
      while (cs)
2141
        {
2142
          enum availability availability;
2143
          bool insufficient = false;
2144
 
2145
          if (cgraph_function_node (cs->callee, &availability) == node
2146
              && availability > AVAIL_OVERWRITABLE
2147
              && cgraph_edge_brings_value_p (cs, src))
2148
            {
2149
              struct ipa_node_params *caller_info;
2150
              struct ipa_edge_args *args;
2151
              int i;
2152
 
2153
              caller_info = IPA_NODE_REF (cs->caller);
2154
              args = IPA_EDGE_REF (cs);
2155
              for (i = 0; i < count; i++)
2156
                {
2157
                  struct ipa_jump_func *jump_func;
2158
                  tree val, t;
2159
 
2160
                  val = VEC_index (tree, dest_info->known_vals, i);
2161
                  if (!val)
2162
                    continue;
2163
 
2164
                  if (i >= ipa_get_cs_argument_count (args))
2165
                    {
2166
                      insufficient = true;
2167
                      break;
2168
                    }
2169
                  jump_func = ipa_get_ith_jump_func (args, i);
2170
                  t = ipa_value_from_jfunc (caller_info, jump_func);
2171
                  if (!t || !values_equal_for_ipcp_p (val, t))
2172
                    {
2173
                      insufficient = true;
2174
                      break;
2175
                    }
2176
                }
2177
 
2178
              if (!insufficient)
2179
                {
2180
                  if (dump_file)
2181
                    fprintf (dump_file, " - adding an extra caller %s/%i"
2182
                             " of %s/%i\n",
2183
                             cgraph_node_name (cs->caller), cs->caller->uid,
2184
                             cgraph_node_name (val->spec_node),
2185
                             val->spec_node->uid);
2186
 
2187
                  cgraph_redirect_edge_callee (cs, val->spec_node);
2188
                  redirected_sum += cs->count;
2189
                }
2190
            }
2191
          cs = get_next_cgraph_edge_clone (cs);
2192
        }
2193
    }
2194
 
2195
  if (redirected_sum)
2196
    update_specialized_profile (val->spec_node, node, redirected_sum);
2197
}
2198
 
2199
 
2200
/* Copy KNOWN_BINFOS to KNOWN_VALS.  */
2201
 
2202
static void
2203
move_binfos_to_values (VEC (tree, heap) *known_vals,
2204
                       VEC (tree, heap) *known_binfos)
2205
{
2206
  tree t;
2207
  int i;
2208
 
2209
  for (i = 0; VEC_iterate (tree, known_binfos, i, t); i++)
2210
    if (t)
2211
      VEC_replace (tree, known_vals, i, t);
2212
}
2213
 
2214
 
2215
/* Decide whether and what specialized clones of NODE should be created.  */
2216
 
2217
static bool
2218
decide_whether_version_node (struct cgraph_node *node)
2219
{
2220
  struct ipa_node_params *info = IPA_NODE_REF (node);
2221
  int i, count = ipa_get_param_count (info);
2222
  VEC (tree, heap) *known_csts, *known_binfos;
2223
  bool ret = false;
2224
 
2225
  if (count == 0)
2226
    return false;
2227
 
2228
  if (dump_file && (dump_flags & TDF_DETAILS))
2229
    fprintf (dump_file, "\nEvaluating opportunities for %s/%i.\n",
2230
             cgraph_node_name (node), node->uid);
2231
 
2232
  gather_context_independent_values (info, &known_csts, &known_binfos,
2233
                                     NULL);
2234
 
2235
  for (i = 0; i < count ; i++)
2236
    {
2237
      struct ipcp_lattice *lat = ipa_get_lattice (info, i);
2238
      struct ipcp_value *val;
2239
 
2240
      if (lat->bottom
2241
          || VEC_index (tree, known_csts, i)
2242
          || VEC_index (tree, known_binfos, i))
2243
        continue;
2244
 
2245
      for (val = lat->values; val; val = val->next)
2246
        {
2247
          int freq_sum, caller_count;
2248
          gcov_type count_sum;
2249
          VEC (cgraph_edge_p, heap) *callers;
2250
          VEC (tree, heap) *kv;
2251
 
2252
          if (val->spec_node)
2253
            {
2254
              perhaps_add_new_callers (node, val);
2255
              continue;
2256
            }
2257
          else if (val->local_size_cost + overall_size > max_new_size)
2258
            {
2259
              if (dump_file && (dump_flags & TDF_DETAILS))
2260
                fprintf (dump_file, "   Ignoring candidate value because "
2261
                         "max_new_size would be reached with %li.\n",
2262
                         val->local_size_cost + overall_size);
2263
              continue;
2264
            }
2265
          else if (!get_info_about_necessary_edges (val, &freq_sum, &count_sum,
2266
                                                    &caller_count))
2267
            continue;
2268
 
2269
          if (dump_file && (dump_flags & TDF_DETAILS))
2270
            {
2271
              fprintf (dump_file, " - considering value ");
2272
              print_ipcp_constant_value (dump_file, val->value);
2273
              fprintf (dump_file, " for parameter ");
2274
              print_generic_expr (dump_file, ipa_get_param (info, i), 0);
2275
              fprintf (dump_file, " (caller_count: %i)\n", caller_count);
2276
            }
2277
 
2278
 
2279
          if (!good_cloning_opportunity_p (node, val->local_time_benefit,
2280
                                           freq_sum, count_sum,
2281
                                           val->local_size_cost)
2282
              && !good_cloning_opportunity_p (node,
2283
                                              val->local_time_benefit
2284
                                              + val->prop_time_benefit,
2285
                                              freq_sum, count_sum,
2286
                                              val->local_size_cost
2287
                                              + val->prop_size_cost))
2288
            continue;
2289
 
2290
          if (dump_file)
2291
            fprintf (dump_file, "  Creating a specialized node of %s/%i.\n",
2292
                     cgraph_node_name (node), node->uid);
2293
 
2294
          callers = gather_edges_for_value (val, caller_count);
2295
          kv = VEC_copy (tree, heap, known_csts);
2296
          move_binfos_to_values (kv, known_binfos);
2297
          VEC_replace (tree, kv, i, val->value);
2298
          find_more_values_for_callers_subset (node, kv, callers);
2299
          val->spec_node = create_specialized_node (node, kv, callers);
2300
          overall_size += val->local_size_cost;
2301
          info = IPA_NODE_REF (node);
2302
 
2303
          /* TODO: If for some lattice there is only one other known value
2304
             left, make a special node for it too. */
2305
          ret = true;
2306
 
2307
          VEC_replace (tree, kv, i, val->value);
2308
        }
2309
    }
2310
 
2311
  if (info->clone_for_all_contexts)
2312
    {
2313
      VEC (cgraph_edge_p, heap) *callers;
2314
 
2315
      if (dump_file)
2316
        fprintf (dump_file, " - Creating a specialized node of %s/%i "
2317
                 "for all known contexts.\n", cgraph_node_name (node),
2318
                 node->uid);
2319
 
2320
      callers = collect_callers_of_node (node);
2321
      move_binfos_to_values (known_csts, known_binfos);
2322
      create_specialized_node (node, known_csts, callers);
2323
      info = IPA_NODE_REF (node);
2324
      info->clone_for_all_contexts = false;
2325
      ret = true;
2326
    }
2327
  else
2328
    VEC_free (tree, heap, known_csts);
2329
 
2330
  VEC_free (tree, heap, known_binfos);
2331
  return ret;
2332
}
2333
 
2334
/* Transitively mark all callees of NODE within the same SCC as not dead.  */
2335
 
2336
static void
2337
spread_undeadness (struct cgraph_node *node)
2338
{
2339
  struct cgraph_edge *cs;
2340
 
2341
  for (cs = node->callees; cs; cs = cs->next_callee)
2342
    if (edge_within_scc (cs))
2343
      {
2344
        struct cgraph_node *callee;
2345
        struct ipa_node_params *info;
2346
 
2347
        callee = cgraph_function_node (cs->callee, NULL);
2348
        info = IPA_NODE_REF (callee);
2349
 
2350
        if (info->node_dead)
2351
          {
2352
            info->node_dead = 0;
2353
            spread_undeadness (callee);
2354
          }
2355
      }
2356
}
2357
 
2358
/* Return true if NODE has a caller from outside of its SCC that is not
2359
   dead.  Worker callback for cgraph_for_node_and_aliases.  */
2360
 
2361
static bool
2362
has_undead_caller_from_outside_scc_p (struct cgraph_node *node,
2363
                                     void *data ATTRIBUTE_UNUSED)
2364
{
2365
  struct cgraph_edge *cs;
2366
 
2367
  for (cs = node->callers; cs; cs = cs->next_caller)
2368
    if (cs->caller->thunk.thunk_p
2369
        && cgraph_for_node_and_aliases (cs->caller,
2370
                                        has_undead_caller_from_outside_scc_p,
2371
                                        NULL, true))
2372
      return true;
2373
    else if (!edge_within_scc (cs)
2374
             && !IPA_NODE_REF (cs->caller)->node_dead)
2375
      return true;
2376
  return false;
2377
}
2378
 
2379
 
2380
/* Identify nodes within the same SCC as NODE which are no longer needed
2381
   because of new clones and will be removed as unreachable.  */
2382
 
2383
static void
2384
identify_dead_nodes (struct cgraph_node *node)
2385
{
2386
  struct cgraph_node *v;
2387
  for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
2388
    if (cgraph_will_be_removed_from_program_if_no_direct_calls (v)
2389
        && !cgraph_for_node_and_aliases (v,
2390
                                         has_undead_caller_from_outside_scc_p,
2391
                                         NULL, true))
2392
      IPA_NODE_REF (v)->node_dead = 1;
2393
 
2394
  for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
2395
    if (!IPA_NODE_REF (v)->node_dead)
2396
      spread_undeadness (v);
2397
 
2398
  if (dump_file && (dump_flags & TDF_DETAILS))
2399
    {
2400
      for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
2401
        if (IPA_NODE_REF (v)->node_dead)
2402
          fprintf (dump_file, "  Marking node as dead: %s/%i.\n",
2403
                   cgraph_node_name (v), v->uid);
2404
    }
2405
}
2406
 
2407
/* The decision stage.  Iterate over the topological order of call graph nodes
2408
   TOPO and make specialized clones if deemed beneficial.  */
2409
 
2410
static void
2411
ipcp_decision_stage (struct topo_info *topo)
2412
{
2413
  int i;
2414
 
2415
  if (dump_file)
2416
    fprintf (dump_file, "\nIPA decision stage:\n\n");
2417
 
2418
  for (i = topo->nnodes - 1; i >= 0; i--)
2419
    {
2420
      struct cgraph_node *node = topo->order[i];
2421
      bool change = false, iterate = true;
2422
 
2423
      while (iterate)
2424
        {
2425
          struct cgraph_node *v;
2426
          iterate = false;
2427
          for (v = node; v ; v = ((struct ipa_dfs_info *) v->aux)->next_cycle)
2428
            if (cgraph_function_with_gimple_body_p (v)
2429
                && ipcp_versionable_function_p (v))
2430
              iterate |= decide_whether_version_node (v);
2431
 
2432
          change |= iterate;
2433
        }
2434
      if (change)
2435
        identify_dead_nodes (node);
2436
    }
2437
}
2438
 
2439
/* The IPCP driver.  */
2440
 
2441
static unsigned int
2442
ipcp_driver (void)
2443
{
2444
  struct cgraph_2edge_hook_list *edge_duplication_hook_holder;
2445
  struct topo_info topo;
2446
 
2447
  cgraph_remove_unreachable_nodes (true,dump_file);
2448
  ipa_check_create_node_params ();
2449
  ipa_check_create_edge_args ();
2450
  grow_next_edge_clone_vector ();
2451
  edge_duplication_hook_holder =
2452
    cgraph_add_edge_duplication_hook (&ipcp_edge_duplication_hook, NULL);
2453
  ipcp_values_pool = create_alloc_pool ("IPA-CP values",
2454
                                        sizeof (struct ipcp_value), 32);
2455
  ipcp_sources_pool = create_alloc_pool ("IPA-CP value sources",
2456
                                         sizeof (struct ipcp_value_source), 64);
2457
  if (dump_file)
2458
    {
2459
      fprintf (dump_file, "\nIPA structures before propagation:\n");
2460
      if (dump_flags & TDF_DETAILS)
2461
        ipa_print_all_params (dump_file);
2462
      ipa_print_all_jump_functions (dump_file);
2463
    }
2464
 
2465
  /* Topological sort.  */
2466
  build_toporder_info (&topo);
2467
  /* Do the interprocedural propagation.  */
2468
  ipcp_propagate_stage (&topo);
2469
  /* Decide what constant propagation and cloning should be performed.  */
2470
  ipcp_decision_stage (&topo);
2471
 
2472
  /* Free all IPCP structures.  */
2473
  free_toporder_info (&topo);
2474
  VEC_free (cgraph_edge_p, heap, next_edge_clone);
2475
  cgraph_remove_edge_duplication_hook (edge_duplication_hook_holder);
2476
  ipa_free_all_structures_after_ipa_cp ();
2477
  if (dump_file)
2478
    fprintf (dump_file, "\nIPA constant propagation end\n");
2479
  return 0;
2480
}
2481
 
2482
/* Initialization and computation of IPCP data structures.  This is the initial
2483
   intraprocedural analysis of functions, which gathers information to be
2484
   propagated later on.  */
2485
 
2486
static void
2487
ipcp_generate_summary (void)
2488
{
2489
  struct cgraph_node *node;
2490
 
2491
  if (dump_file)
2492
    fprintf (dump_file, "\nIPA constant propagation start:\n");
2493
  ipa_register_cgraph_hooks ();
2494
 
2495
  FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
2496
      {
2497
        /* Unreachable nodes should have been eliminated before ipcp.  */
2498
        gcc_assert (node->needed || node->reachable);
2499
        node->local.versionable = tree_versionable_function_p (node->decl);
2500
        ipa_analyze_node (node);
2501
      }
2502
}
2503
 
2504
/* Write ipcp summary for nodes in SET.  */
2505
 
2506
static void
2507
ipcp_write_summary (cgraph_node_set set,
2508
                    varpool_node_set vset ATTRIBUTE_UNUSED)
2509
{
2510
  ipa_prop_write_jump_functions (set);
2511
}
2512
 
2513
/* Read ipcp summary.  */
2514
 
2515
static void
2516
ipcp_read_summary (void)
2517
{
2518
  ipa_prop_read_jump_functions ();
2519
}
2520
 
2521
/* Gate for IPCP optimization.  */
2522
 
2523
static bool
2524
cgraph_gate_cp (void)
2525
{
2526
  /* FIXME: We should remove the optimize check after we ensure we never run
2527
     IPA passes when not optimizing.  */
2528
  return flag_ipa_cp && optimize;
2529
}
2530
 
2531
struct ipa_opt_pass_d pass_ipa_cp =
2532
{
2533
 {
2534
  IPA_PASS,
2535
  "cp",                         /* name */
2536
  cgraph_gate_cp,               /* gate */
2537
  ipcp_driver,                  /* execute */
2538
  NULL,                         /* sub */
2539
  NULL,                         /* next */
2540
  0,                             /* static_pass_number */
2541
  TV_IPA_CONSTANT_PROP,         /* tv_id */
2542
  0,                             /* properties_required */
2543
  0,                             /* properties_provided */
2544
  0,                             /* properties_destroyed */
2545
  0,                             /* todo_flags_start */
2546
  TODO_dump_cgraph |
2547
  TODO_remove_functions | TODO_ggc_collect /* todo_flags_finish */
2548
 },
2549
 ipcp_generate_summary,                 /* generate_summary */
2550
 ipcp_write_summary,                    /* write_summary */
2551
 ipcp_read_summary,                     /* read_summary */
2552
 NULL,                                  /* write_optimization_summary */
2553
 NULL,                                  /* read_optimization_summary */
2554
 NULL,                                  /* stmt_fixup */
2555
 0,                                      /* TODOs */
2556
 NULL,                                  /* function_transform */
2557
 NULL,                                  /* variable_transform */
2558
};

powered by: WebSVN 2.1.0

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