mirrored from git://gcc.gnu.org/git/gcc.git
/
ipa-cp.c
6640 lines (5721 loc) · 196 KB
/
ipa-cp.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/* Interprocedural constant propagation
Copyright (C) 2005-2021 Free Software Foundation, Inc.
Contributed by Razya Ladelsky <RAZYA@il.ibm.com> and Martin Jambor
<mjambor@suse.cz>
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
/* Interprocedural constant propagation (IPA-CP).
The goal of this transformation is to
1) discover functions which are always invoked with some arguments with the
same known constant values and modify the functions so that the
subsequent optimizations can take advantage of the knowledge, and
2) partial specialization - create specialized versions of functions
transformed in this way if some parameters are known constants only in
certain contexts but the estimated tradeoff between speedup and cost size
is deemed good.
The algorithm also propagates types and attempts to perform type based
devirtualization. Types are propagated much like constants.
The algorithm basically consists of three stages. In the first, functions
are analyzed one at a time and jump functions are constructed for all known
call-sites. In the second phase, the pass propagates information from the
jump functions across the call to reveal what values are available at what
call sites, performs estimations of effects of known values on functions and
their callees, and finally decides what specialized extra versions should be
created. In the third, the special versions materialize and appropriate
calls are redirected.
The algorithm used is to a certain extent based on "Interprocedural Constant
Propagation", by David Callahan, Keith D Cooper, Ken Kennedy, Linda Torczon,
Comp86, pg 152-161 and "A Methodology for Procedure Cloning" by Keith D
Cooper, Mary W. Hall, and Ken Kennedy.
First stage - intraprocedural analysis
=======================================
This phase computes jump_function and modification flags.
A jump function for a call-site represents the values passed as an actual
arguments of a given call-site. In principle, there are three types of
values:
Pass through - the caller's formal parameter is passed as an actual
argument, plus an operation on it can be performed.
Constant - a constant is passed as an actual argument.
Unknown - neither of the above.
All jump function types are described in detail in ipa-prop.h, together with
the data structures that represent them and methods of accessing them.
ipcp_generate_summary() is the main function of the first stage.
Second stage - interprocedural analysis
========================================
This stage is itself divided into two phases. In the first, we propagate
known values over the call graph, in the second, we make cloning decisions.
It uses a different algorithm than the original Callahan's paper.
First, we traverse the functions topologically from callers to callees and,
for each strongly connected component (SCC), we propagate constants
according to previously computed jump functions. We also record what known
values depend on other known values and estimate local effects. Finally, we
propagate cumulative information about these effects from dependent values
to those on which they depend.
Second, we again traverse the call graph in the same topological order and
make clones for functions which we know are called with the same values in
all contexts and decide about extra specialized clones of functions just for
some contexts - these decisions are based on both local estimates and
cumulative estimates propagated from callees.
ipcp_propagate_stage() and ipcp_decision_stage() together constitute the
third stage.
Third phase - materialization of clones, call statement updates.
============================================
This stage is currently performed by call graph code (mainly in cgraphunit.c
and tree-inline.c) according to instructions inserted to the call graph by
the second stage. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple-expr.h"
#include "gimple.h"
#include "predict.h"
#include "alloc-pool.h"
#include "tree-pass.h"
#include "cgraph.h"
#include "diagnostic.h"
#include "fold-const.h"
#include "gimple-fold.h"
#include "symbol-summary.h"
#include "tree-vrp.h"
#include "ipa-prop.h"
#include "tree-pretty-print.h"
#include "tree-inline.h"
#include "ipa-fnsummary.h"
#include "ipa-utils.h"
#include "tree-ssa-ccp.h"
#include "stringpool.h"
#include "attribs.h"
#include "dbgcnt.h"
#include "symtab-clones.h"
template <typename valtype> class ipcp_value;
/* Describes a particular source for an IPA-CP value. */
template <typename valtype>
struct ipcp_value_source
{
public:
/* Aggregate offset of the source, negative if the source is scalar value of
the argument itself. */
HOST_WIDE_INT offset;
/* The incoming edge that brought the value. */
cgraph_edge *cs;
/* If the jump function that resulted into his value was a pass-through or an
ancestor, this is the ipcp_value of the caller from which the described
value has been derived. Otherwise it is NULL. */
ipcp_value<valtype> *val;
/* Next pointer in a linked list of sources of a value. */
ipcp_value_source *next;
/* If the jump function that resulted into his value was a pass-through or an
ancestor, this is the index of the parameter of the caller the jump
function references. */
int index;
};
/* Common ancestor for all ipcp_value instantiations. */
class ipcp_value_base
{
public:
/* Time benefit and that specializing the function for this value would bring
about in this function alone. */
sreal local_time_benefit;
/* Time benefit that specializing the function for this value can bring about
in it's callees. */
sreal prop_time_benefit;
/* Size cost that specializing the function for this value would bring about
in this function alone. */
int local_size_cost;
/* Size cost that specializing the function for this value can bring about in
it's callees. */
int prop_size_cost;
ipcp_value_base ()
: local_time_benefit (0), prop_time_benefit (0),
local_size_cost (0), prop_size_cost (0) {}
};
/* Describes one particular value stored in struct ipcp_lattice. */
template <typename valtype>
class ipcp_value : public ipcp_value_base
{
public:
/* The actual value for the given parameter. */
valtype value;
/* The list of sources from which this value originates. */
ipcp_value_source <valtype> *sources = nullptr;
/* Next pointers in a linked list of all values in a lattice. */
ipcp_value *next = nullptr;
/* Next pointers in a linked list of values in a strongly connected component
of values. */
ipcp_value *scc_next = nullptr;
/* Next pointers in a linked list of SCCs of values sorted topologically
according their sources. */
ipcp_value *topo_next = nullptr;
/* A specialized node created for this value, NULL if none has been (so far)
created. */
cgraph_node *spec_node = nullptr;
/* Depth first search number and low link for topological sorting of
values. */
int dfs = 0;
int low_link = 0;
/* SCC number to identify values which recursively feed into each other.
Values in the same SCC have the same SCC number. */
int scc_no = 0;
/* Non zero if the value is generated from another value in the same lattice
for a self-recursive call, the actual number is how many times the
operation has been performed. In the unlikely event of the value being
present in two chains fo self-recursive value generation chains, it is the
maximum. */
unsigned self_recursion_generated_level = 0;
/* True if this value is currently on the topo-sort stack. */
bool on_stack = false;
void add_source (cgraph_edge *cs, ipcp_value *src_val, int src_idx,
HOST_WIDE_INT offset);
/* Return true if both THIS value and O feed into each other. */
bool same_scc (const ipcp_value<valtype> *o)
{
return o->scc_no == scc_no;
}
/* Return true, if a this value has been generated for a self-recursive call as
a result of an arithmetic pass-through jump-function acting on a value in
the same lattice function. */
bool self_recursion_generated_p ()
{
return self_recursion_generated_level > 0;
}
};
/* Lattice describing potential values of a formal parameter of a function, or
a part of an aggregate. TOP is represented by a lattice with zero values
and with contains_variable and bottom flags cleared. BOTTOM is represented
by a lattice with the bottom flag set. In that case, values and
contains_variable flag should be disregarded. */
template <typename valtype>
struct ipcp_lattice
{
public:
/* The list of known values and types in this lattice. Note that values are
not deallocated if a lattice is set to bottom because there may be value
sources referencing them. */
ipcp_value<valtype> *values;
/* Number of known values and types in this lattice. */
int values_count;
/* The lattice contains a variable component (in addition to values). */
bool contains_variable;
/* The value of the lattice is bottom (i.e. variable and unusable for any
propagation). */
bool bottom;
inline bool is_single_const ();
inline bool set_to_bottom ();
inline bool set_contains_variable ();
bool add_value (valtype newval, cgraph_edge *cs,
ipcp_value<valtype> *src_val = NULL,
int src_idx = 0, HOST_WIDE_INT offset = -1,
ipcp_value<valtype> **val_p = NULL,
unsigned same_lat_gen_level = 0);
void print (FILE * f, bool dump_sources, bool dump_benefits);
};
/* Lattice of tree values with an offset to describe a part of an
aggregate. */
struct ipcp_agg_lattice : public ipcp_lattice<tree>
{
public:
/* Offset that is being described by this lattice. */
HOST_WIDE_INT offset;
/* Size so that we don't have to re-compute it every time we traverse the
list. Must correspond to TYPE_SIZE of all lat values. */
HOST_WIDE_INT size;
/* Next element of the linked list. */
struct ipcp_agg_lattice *next;
};
/* Lattice of known bits, only capable of holding one value.
Bitwise constant propagation propagates which bits of a
value are constant.
For eg:
int f(int x)
{
return some_op (x);
}
int f1(int y)
{
if (cond)
return f (y & 0xff);
else
return f (y & 0xf);
}
In the above case, the param 'x' will always have all
the bits (except the bits in lsb) set to 0.
Hence the mask of 'x' would be 0xff. The mask
reflects that the bits in lsb are unknown.
The actual propagated value is given by m_value & ~m_mask. */
class ipcp_bits_lattice
{
public:
bool bottom_p () { return m_lattice_val == IPA_BITS_VARYING; }
bool top_p () { return m_lattice_val == IPA_BITS_UNDEFINED; }
bool constant_p () { return m_lattice_val == IPA_BITS_CONSTANT; }
bool set_to_bottom ();
bool set_to_constant (widest_int, widest_int);
widest_int get_value () { return m_value; }
widest_int get_mask () { return m_mask; }
bool meet_with (ipcp_bits_lattice& other, unsigned, signop,
enum tree_code, tree);
bool meet_with (widest_int, widest_int, unsigned);
void print (FILE *);
private:
enum { IPA_BITS_UNDEFINED, IPA_BITS_CONSTANT, IPA_BITS_VARYING } m_lattice_val;
/* Similar to ccp_lattice_t, mask represents which bits of value are constant.
If a bit in mask is set to 0, then the corresponding bit in
value is known to be constant. */
widest_int m_value, m_mask;
bool meet_with_1 (widest_int, widest_int, unsigned);
void get_value_and_mask (tree, widest_int *, widest_int *);
};
/* Lattice of value ranges. */
class ipcp_vr_lattice
{
public:
value_range m_vr;
inline bool bottom_p () const;
inline bool top_p () const;
inline bool set_to_bottom ();
bool meet_with (const value_range *p_vr);
bool meet_with (const ipcp_vr_lattice &other);
void init () { gcc_assert (m_vr.undefined_p ()); }
void print (FILE * f);
private:
bool meet_with_1 (const value_range *other_vr);
};
/* Structure containing lattices for a parameter itself and for pieces of
aggregates that are passed in the parameter or by a reference in a parameter
plus some other useful flags. */
class ipcp_param_lattices
{
public:
/* Lattice describing the value of the parameter itself. */
ipcp_lattice<tree> itself;
/* Lattice describing the polymorphic contexts of a parameter. */
ipcp_lattice<ipa_polymorphic_call_context> ctxlat;
/* Lattices describing aggregate parts. */
ipcp_agg_lattice *aggs;
/* Lattice describing known bits. */
ipcp_bits_lattice bits_lattice;
/* Lattice describing value range. */
ipcp_vr_lattice m_value_range;
/* Number of aggregate lattices */
int aggs_count;
/* True if aggregate data were passed by reference (as opposed to by
value). */
bool aggs_by_ref;
/* All aggregate lattices contain a variable component (in addition to
values). */
bool aggs_contain_variable;
/* The value of all aggregate lattices is bottom (i.e. variable and unusable
for any propagation). */
bool aggs_bottom;
/* There is a virtual call based on this parameter. */
bool virt_call;
};
/* Allocation pools for values and their sources in ipa-cp. */
object_allocator<ipcp_value<tree> > ipcp_cst_values_pool
("IPA-CP constant values");
object_allocator<ipcp_value<ipa_polymorphic_call_context> >
ipcp_poly_ctx_values_pool ("IPA-CP polymorphic contexts");
object_allocator<ipcp_value_source<tree> > ipcp_sources_pool
("IPA-CP value sources");
object_allocator<ipcp_agg_lattice> ipcp_agg_lattice_pool
("IPA_CP aggregate lattices");
/* Base count to use in heuristics when using profile feedback. */
static profile_count base_count;
/* Original overall size of the program. */
static long overall_size, orig_overall_size;
/* Node name to unique clone suffix number map. */
static hash_map<const char *, unsigned> *clone_num_suffixes;
/* Return the param lattices structure corresponding to the Ith formal
parameter of the function described by INFO. */
static inline class ipcp_param_lattices *
ipa_get_parm_lattices (class ipa_node_params *info, int i)
{
gcc_assert (i >= 0 && i < ipa_get_param_count (info));
gcc_checking_assert (!info->ipcp_orig_node);
gcc_checking_assert (info->lattices);
return &(info->lattices[i]);
}
/* Return the lattice corresponding to the scalar value of the Ith formal
parameter of the function described by INFO. */
static inline ipcp_lattice<tree> *
ipa_get_scalar_lat (class ipa_node_params *info, int i)
{
class ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
return &plats->itself;
}
/* Return the lattice corresponding to the scalar value of the Ith formal
parameter of the function described by INFO. */
static inline ipcp_lattice<ipa_polymorphic_call_context> *
ipa_get_poly_ctx_lat (class ipa_node_params *info, int i)
{
class ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
return &plats->ctxlat;
}
/* Return whether LAT is a lattice with a single constant and without an
undefined value. */
template <typename valtype>
inline bool
ipcp_lattice<valtype>::is_single_const ()
{
if (bottom || contains_variable || values_count != 1)
return false;
else
return true;
}
/* Print V which is extracted from a value in a lattice to F. */
static void
print_ipcp_constant_value (FILE * f, tree v)
{
if (TREE_CODE (v) == ADDR_EXPR
&& TREE_CODE (TREE_OPERAND (v, 0)) == CONST_DECL)
{
fprintf (f, "& ");
print_generic_expr (f, DECL_INITIAL (TREE_OPERAND (v, 0)));
}
else
print_generic_expr (f, v);
}
/* Print V which is extracted from a value in a lattice to F. */
static void
print_ipcp_constant_value (FILE * f, ipa_polymorphic_call_context v)
{
v.dump(f, false);
}
/* Print a lattice LAT to F. */
template <typename valtype>
void
ipcp_lattice<valtype>::print (FILE * f, bool dump_sources, bool dump_benefits)
{
ipcp_value<valtype> *val;
bool prev = false;
if (bottom)
{
fprintf (f, "BOTTOM\n");
return;
}
if (!values_count && !contains_variable)
{
fprintf (f, "TOP\n");
return;
}
if (contains_variable)
{
fprintf (f, "VARIABLE");
prev = true;
if (dump_benefits)
fprintf (f, "\n");
}
for (val = values; val; val = val->next)
{
if (dump_benefits && prev)
fprintf (f, " ");
else if (!dump_benefits && prev)
fprintf (f, ", ");
else
prev = true;
print_ipcp_constant_value (f, val->value);
if (dump_sources)
{
ipcp_value_source<valtype> *s;
if (val->self_recursion_generated_p ())
fprintf (f, " [self_gen(%i), from:",
val->self_recursion_generated_level);
else
fprintf (f, " [scc: %i, from:", val->scc_no);
for (s = val->sources; s; s = s->next)
fprintf (f, " %i(%f)", s->cs->caller->order,
s->cs->sreal_frequency ().to_double ());
fprintf (f, "]");
}
if (dump_benefits)
fprintf (f, " [loc_time: %g, loc_size: %i, "
"prop_time: %g, prop_size: %i]\n",
val->local_time_benefit.to_double (), val->local_size_cost,
val->prop_time_benefit.to_double (), val->prop_size_cost);
}
if (!dump_benefits)
fprintf (f, "\n");
}
void
ipcp_bits_lattice::print (FILE *f)
{
if (top_p ())
fprintf (f, " Bits unknown (TOP)\n");
else if (bottom_p ())
fprintf (f, " Bits unusable (BOTTOM)\n");
else
{
fprintf (f, " Bits: value = "); print_hex (get_value (), f);
fprintf (f, ", mask = "); print_hex (get_mask (), f);
fprintf (f, "\n");
}
}
/* Print value range lattice to F. */
void
ipcp_vr_lattice::print (FILE * f)
{
dump_value_range (f, &m_vr);
}
/* Print all ipcp_lattices of all functions to F. */
static void
print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits)
{
struct cgraph_node *node;
int i, count;
fprintf (f, "\nLattices:\n");
FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node)
{
class ipa_node_params *info;
info = ipa_node_params_sum->get (node);
/* Skip unoptimized functions and constprop clones since we don't make
lattices for them. */
if (!info || info->ipcp_orig_node)
continue;
fprintf (f, " Node: %s:\n", node->dump_name ());
count = ipa_get_param_count (info);
for (i = 0; i < count; i++)
{
struct ipcp_agg_lattice *aglat;
class ipcp_param_lattices *plats = ipa_get_parm_lattices (info, i);
fprintf (f, " param [%d]: ", i);
plats->itself.print (f, dump_sources, dump_benefits);
fprintf (f, " ctxs: ");
plats->ctxlat.print (f, dump_sources, dump_benefits);
plats->bits_lattice.print (f);
fprintf (f, " ");
plats->m_value_range.print (f);
fprintf (f, "\n");
if (plats->virt_call)
fprintf (f, " virt_call flag set\n");
if (plats->aggs_bottom)
{
fprintf (f, " AGGS BOTTOM\n");
continue;
}
if (plats->aggs_contain_variable)
fprintf (f, " AGGS VARIABLE\n");
for (aglat = plats->aggs; aglat; aglat = aglat->next)
{
fprintf (f, " %soffset " HOST_WIDE_INT_PRINT_DEC ": ",
plats->aggs_by_ref ? "ref " : "", aglat->offset);
aglat->print (f, dump_sources, dump_benefits);
}
}
}
}
/* Determine whether it is at all technically possible to create clones of NODE
and store this information in the ipa_node_params structure associated
with NODE. */
static void
determine_versionability (struct cgraph_node *node,
class ipa_node_params *info)
{
const char *reason = NULL;
/* There are a number of generic reasons functions cannot be versioned. We
also cannot remove parameters if there are type attributes such as fnspec
present. */
if (node->alias || node->thunk)
reason = "alias or thunk";
else if (!node->versionable)
reason = "not a tree_versionable_function";
else if (node->get_availability () <= AVAIL_INTERPOSABLE)
reason = "insufficient body availability";
else if (!opt_for_fn (node->decl, optimize)
|| !opt_for_fn (node->decl, flag_ipa_cp))
reason = "non-optimized function";
else if (lookup_attribute ("omp declare simd", DECL_ATTRIBUTES (node->decl)))
{
/* Ideally we should clone the SIMD clones themselves and create
vector copies of them, so IPA-cp and SIMD clones can happily
coexist, but that may not be worth the effort. */
reason = "function has SIMD clones";
}
else if (lookup_attribute ("target_clones", DECL_ATTRIBUTES (node->decl)))
{
/* Ideally we should clone the target clones themselves and create
copies of them, so IPA-cp and target clones can happily
coexist, but that may not be worth the effort. */
reason = "function target_clones attribute";
}
/* Don't clone decls local to a comdat group; it breaks and for C++
decloned constructors, inlining is always better anyway. */
else if (node->comdat_local_p ())
reason = "comdat-local function";
else if (node->calls_comdat_local)
{
/* TODO: call is versionable if we make sure that all
callers are inside of a comdat group. */
reason = "calls comdat-local function";
}
/* Functions calling BUILT_IN_VA_ARG_PACK and BUILT_IN_VA_ARG_PACK_LEN
work only when inlined. Cloning them may still lead to better code
because ipa-cp will not give up on cloning further. If the function is
external this however leads to wrong code because we may end up producing
offline copy of the function. */
if (DECL_EXTERNAL (node->decl))
for (cgraph_edge *edge = node->callees; !reason && edge;
edge = edge->next_callee)
if (fndecl_built_in_p (edge->callee->decl, BUILT_IN_NORMAL))
{
if (DECL_FUNCTION_CODE (edge->callee->decl) == BUILT_IN_VA_ARG_PACK)
reason = "external function which calls va_arg_pack";
if (DECL_FUNCTION_CODE (edge->callee->decl)
== BUILT_IN_VA_ARG_PACK_LEN)
reason = "external function which calls va_arg_pack_len";
}
if (reason && dump_file && !node->alias && !node->thunk)
fprintf (dump_file, "Function %s is not versionable, reason: %s.\n",
node->dump_name (), reason);
info->versionable = (reason == NULL);
}
/* Return true if it is at all technically possible to create clones of a
NODE. */
static bool
ipcp_versionable_function_p (struct cgraph_node *node)
{
ipa_node_params *info = ipa_node_params_sum->get (node);
return info && info->versionable;
}
/* Structure holding accumulated information about callers of a node. */
struct caller_statistics
{
/* If requested (see below), self-recursive call counts are summed into this
field. */
profile_count rec_count_sum;
/* The sum of all ipa counts of all the other (non-recursive) calls. */
profile_count count_sum;
/* Sum of all frequencies for all calls. */
sreal freq_sum;
/* Number of calls and hot calls respectively. */
int n_calls, n_hot_calls;
/* If itself is set up, also count the number of non-self-recursive
calls. */
int n_nonrec_calls;
/* If non-NULL, this is the node itself and calls from it should have their
counts included in rec_count_sum and not count_sum. */
cgraph_node *itself;
};
/* Initialize fields of STAT to zeroes and optionally set it up so that edges
from IGNORED_CALLER are not counted. */
static inline void
init_caller_stats (caller_statistics *stats, cgraph_node *itself = NULL)
{
stats->rec_count_sum = profile_count::zero ();
stats->count_sum = profile_count::zero ();
stats->n_calls = 0;
stats->n_hot_calls = 0;
stats->n_nonrec_calls = 0;
stats->freq_sum = 0;
stats->itself = itself;
}
/* Worker callback of cgraph_for_node_and_aliases accumulating statistics of
non-thunk incoming edges to NODE. */
static bool
gather_caller_stats (struct cgraph_node *node, void *data)
{
struct caller_statistics *stats = (struct caller_statistics *) data;
struct cgraph_edge *cs;
for (cs = node->callers; cs; cs = cs->next_caller)
if (!cs->caller->thunk)
{
ipa_node_params *info = ipa_node_params_sum->get (cs->caller);
if (info && info->node_dead)
continue;
if (cs->count.ipa ().initialized_p ())
{
if (stats->itself && stats->itself == cs->caller)
stats->rec_count_sum += cs->count.ipa ();
else
stats->count_sum += cs->count.ipa ();
}
stats->freq_sum += cs->sreal_frequency ();
stats->n_calls++;
if (stats->itself && stats->itself != cs->caller)
stats->n_nonrec_calls++;
if (cs->maybe_hot_p ())
stats->n_hot_calls ++;
}
return false;
}
/* Return true if this NODE is viable candidate for cloning. */
static bool
ipcp_cloning_candidate_p (struct cgraph_node *node)
{
struct caller_statistics stats;
gcc_checking_assert (node->has_gimple_body_p ());
if (!opt_for_fn (node->decl, flag_ipa_cp_clone))
{
if (dump_file)
fprintf (dump_file, "Not considering %s for cloning; "
"-fipa-cp-clone disabled.\n",
node->dump_name ());
return false;
}
if (node->optimize_for_size_p ())
{
if (dump_file)
fprintf (dump_file, "Not considering %s for cloning; "
"optimizing it for size.\n",
node->dump_name ());
return false;
}
init_caller_stats (&stats);
node->call_for_symbol_thunks_and_aliases (gather_caller_stats, &stats, false);
if (ipa_size_summaries->get (node)->self_size < stats.n_calls)
{
if (dump_file)
fprintf (dump_file, "Considering %s for cloning; code might shrink.\n",
node->dump_name ());
return true;
}
/* When profile is available and function is hot, propagate into it even if
calls seems cold; constant propagation can improve function's speed
significantly. */
if (stats.count_sum > profile_count::zero ()
&& node->count.ipa ().initialized_p ())
{
if (stats.count_sum > node->count.ipa ().apply_scale (90, 100))
{
if (dump_file)
fprintf (dump_file, "Considering %s for cloning; "
"usually called directly.\n",
node->dump_name ());
return true;
}
}
if (!stats.n_hot_calls)
{
if (dump_file)
fprintf (dump_file, "Not considering %s for cloning; no hot calls.\n",
node->dump_name ());
return false;
}
if (dump_file)
fprintf (dump_file, "Considering %s for cloning.\n",
node->dump_name ());
return true;
}
template <typename valtype>
class value_topo_info
{
public:
/* Head of the linked list of topologically sorted values. */
ipcp_value<valtype> *values_topo;
/* Stack for creating SCCs, represented by a linked list too. */
ipcp_value<valtype> *stack;
/* Counter driving the algorithm in add_val_to_toposort. */
int dfs_counter;
value_topo_info () : values_topo (NULL), stack (NULL), dfs_counter (0)
{}
void add_val (ipcp_value<valtype> *cur_val);
void propagate_effects ();
};
/* Arrays representing a topological ordering of call graph nodes and a stack
of nodes used during constant propagation and also data required to perform
topological sort of values and propagation of benefits in the determined
order. */
class ipa_topo_info
{
public:
/* Array with obtained topological order of cgraph nodes. */
struct cgraph_node **order;
/* Stack of cgraph nodes used during propagation within SCC until all values
in the SCC stabilize. */
struct cgraph_node **stack;
int nnodes, stack_top;
value_topo_info<tree> constants;
value_topo_info<ipa_polymorphic_call_context> contexts;
ipa_topo_info () : order(NULL), stack(NULL), nnodes(0), stack_top(0),
constants ()
{}
};
/* Skip edges from and to nodes without ipa_cp enabled.
Ignore not available symbols. */
static bool
ignore_edge_p (cgraph_edge *e)
{
enum availability avail;
cgraph_node *ultimate_target
= e->callee->function_or_virtual_thunk_symbol (&avail, e->caller);
return (avail <= AVAIL_INTERPOSABLE
|| !opt_for_fn (ultimate_target->decl, optimize)
|| !opt_for_fn (ultimate_target->decl, flag_ipa_cp));
}
/* Allocate the arrays in TOPO and topologically sort the nodes into order. */
static void
build_toporder_info (class ipa_topo_info *topo)
{
topo->order = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
topo->stack = XCNEWVEC (struct cgraph_node *, symtab->cgraph_count);
gcc_checking_assert (topo->stack_top == 0);
topo->nnodes = ipa_reduced_postorder (topo->order, true,
ignore_edge_p);
}
/* Free information about strongly connected components and the arrays in
TOPO. */
static void
free_toporder_info (class ipa_topo_info *topo)
{
ipa_free_postorder_info ();
free (topo->order);
free (topo->stack);
}
/* Add NODE to the stack in TOPO, unless it is already there. */
static inline void
push_node_to_stack (class ipa_topo_info *topo, struct cgraph_node *node)
{
ipa_node_params *info = ipa_node_params_sum->get (node);
if (info->node_enqueued)
return;
info->node_enqueued = 1;
topo->stack[topo->stack_top++] = node;
}
/* Pop a node from the stack in TOPO and return it or return NULL if the stack
is empty. */
static struct cgraph_node *
pop_node_from_stack (class ipa_topo_info *topo)
{
if (topo->stack_top)
{
struct cgraph_node *node;
topo->stack_top--;
node = topo->stack[topo->stack_top];
ipa_node_params_sum->get (node)->node_enqueued = 0;
return node;
}
else
return NULL;
}
/* Set lattice LAT to bottom and return true if it previously was not set as
such. */
template <typename valtype>
inline bool
ipcp_lattice<valtype>::set_to_bottom ()
{
bool ret = !bottom;
bottom = true;
return ret;
}
/* Mark lattice as containing an unknown value and return true if it previously
was not marked as such. */
template <typename valtype>
inline bool
ipcp_lattice<valtype>::set_contains_variable ()
{
bool ret = !contains_variable;
contains_variable = true;
return ret;
}
/* Set all aggregate lattices in PLATS to bottom and return true if they were
not previously set as such. */
static inline bool
set_agg_lats_to_bottom (class ipcp_param_lattices *plats)
{
bool ret = !plats->aggs_bottom;
plats->aggs_bottom = true;
return ret;
}
/* Mark all aggregate lattices in PLATS as containing an unknown value and
return true if they were not previously marked as such. */
static inline bool
set_agg_lats_contain_variable (class ipcp_param_lattices *plats)
{
bool ret = !plats->aggs_contain_variable;
plats->aggs_contain_variable = true;
return ret;
}
bool
ipcp_vr_lattice::meet_with (const ipcp_vr_lattice &other)
{
return meet_with_1 (&other.m_vr);
}
/* Meet the current value of the lattice with value range described by VR
lattice. */