forked from illumos/gcc
-
Notifications
You must be signed in to change notification settings - Fork 1
/
ipa-type-escape.c
2215 lines (1883 loc) · 61.3 KB
/
ipa-type-escape.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
/* Type based alias analysis.
Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
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/>. */
/* This pass determines which types in the program contain only
instances that are completely encapsulated by the compilation unit.
Those types that are encapsulated must also pass the further
requirement that there be no bad operations on any instances of
those types.
A great deal of freedom in compilation is allowed for the instances
of those types that pass these conditions.
*/
/* The code in this module is called by the ipa pass manager. It
should be one of the later passes since its information is used by
the rest of the compilation. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "tree-flow.h"
#include "tree-inline.h"
#include "tree-pass.h"
#include "langhooks.h"
#include "pointer-set.h"
#include "ggc.h"
#include "ipa-utils.h"
#include "ipa-type-escape.h"
#include "c-common.h"
#include "tree-gimple.h"
#include "cgraph.h"
#include "output.h"
#include "flags.h"
#include "timevar.h"
#include "diagnostic.h"
#include "langhooks.h"
/* Some of the aliasing is called very early, before this phase is
called. To assure that this is not a problem, we keep track of if
this phase has been run. */
static bool initialized = false;
/* Scratch bitmap for avoiding work. */
static bitmap been_there_done_that;
static bitmap bitmap_tmp;
/* There are two levels of escape that types can undergo.
EXPOSED_PARAMETER - some instance of the variable is
passed by value into an externally visible function or some
instance of the variable is passed out of an externally visible
function as a return value. In this case any of the fields of the
variable that are pointer types end up having their types marked as
FULL_ESCAPE.
FULL_ESCAPE - when bad things happen to good types. One of the
following things happens to the type: (a) either an instance of the
variable has its address passed to an externally visible function,
(b) the address is taken and some bad cast happens to the address
or (c) explicit arithmetic is done to the address.
*/
enum escape_t
{
EXPOSED_PARAMETER,
FULL_ESCAPE
};
/* The following two bit vectors global_types_* correspond to
previous cases above. During the analysis phase, a bit is set in
one of these vectors if an operation of the offending class is
discovered to happen on the associated type. */
static bitmap global_types_exposed_parameter;
static bitmap global_types_full_escape;
/* All of the types seen in this compilation unit. */
static bitmap global_types_seen;
/* Reverse map to take a canon uid and map it to a canon type. Uid's
are never manipulated unless they are associated with a canon
type. */
static splay_tree uid_to_canon_type;
/* Internal structure of type mapping code. This maps a canon type
name to its canon type. */
static splay_tree all_canon_types;
/* Map from type clones to the single canon type. */
static splay_tree type_to_canon_type;
/* A splay tree of bitmaps. An element X in the splay tree has a bit
set in its bitmap at TYPE_UID (TYPE_MAIN_VARIANT (Y)) if there was
an operation in the program of the form "&X.Y". */
static splay_tree uid_to_addressof_down_map;
/* A splay tree of bitmaps. An element Y in the splay tree has a bit
set in its bitmap at TYPE_UID (TYPE_MAIN_VARIANT (X)) if there was
an operation in the program of the form "&X.Y". */
static splay_tree uid_to_addressof_up_map;
/* Tree to hold the subtype maps used to mark subtypes of escaped
types. */
static splay_tree uid_to_subtype_map;
/* Records tree nodes seen in cgraph_create_edges. Simply using
walk_tree_without_duplicates doesn't guarantee each node is visited
once because it gets a new htab upon each recursive call from
scan_for_refs. */
static struct pointer_set_t *visited_nodes;
/* Visited stmts by walk_use_def_chains function because it's called
recursively. */
static struct pointer_set_t *visited_stmts;
static bitmap_obstack ipa_obstack;
/* Static functions from this file that are used
before being defined. */
static unsigned int look_for_casts (tree lhs ATTRIBUTE_UNUSED, tree);
static bool is_cast_from_non_pointer (tree, tree, void *);
/* Get the name of TYPE or return the string "<UNNAMED>". */
static const char*
get_name_of_type (tree type)
{
tree name = TYPE_NAME (type);
if (!name)
/* Unnamed type, do what you like here. */
return "<UNNAMED>";
/* It will be a TYPE_DECL in the case of a typedef, otherwise, an
identifier_node */
if (TREE_CODE (name) == TYPE_DECL)
{
/* Each DECL has a DECL_NAME field which contains an
IDENTIFIER_NODE. (Some decls, most often labels, may have
zero as the DECL_NAME). */
if (DECL_NAME (name))
return IDENTIFIER_POINTER (DECL_NAME (name));
else
/* Unnamed type, do what you like here. */
return "<UNNAMED>";
}
else if (TREE_CODE (name) == IDENTIFIER_NODE)
return IDENTIFIER_POINTER (name);
else
return "<UNNAMED>";
}
struct type_brand_s
{
const char* name;
int seq;
};
/* Splay tree comparison function on type_brand_s structures. */
static int
compare_type_brand (splay_tree_key sk1, splay_tree_key sk2)
{
struct type_brand_s * k1 = (struct type_brand_s *) sk1;
struct type_brand_s * k2 = (struct type_brand_s *) sk2;
int value = strcmp(k1->name, k2->name);
if (value == 0)
return k2->seq - k1->seq;
else
return value;
}
/* All of the "unique_type" code is a hack to get around the sleazy
implementation used to compile more than file. Currently gcc does
not get rid of multiple instances of the same type that have been
collected from different compilation units. */
/* This is a trivial algorithm for removing duplicate types. This
would not work for any language that used structural equivalence as
the basis of its type system. */
/* Return TYPE if no type compatible with TYPE has been seen so far,
otherwise return a type compatible with TYPE that has already been
processed. */
static tree
discover_unique_type (tree type)
{
struct type_brand_s * brand = XNEW (struct type_brand_s);
int i = 0;
splay_tree_node result;
brand->name = get_name_of_type (type);
while (1)
{
brand->seq = i++;
result = splay_tree_lookup (all_canon_types, (splay_tree_key) brand);
if (result)
{
/* Create an alias since this is just the same as
other_type. */
tree other_type = (tree) result->value;
if (types_compatible_p (type, other_type))
{
free (brand);
/* Insert this new type as an alias for other_type. */
splay_tree_insert (type_to_canon_type,
(splay_tree_key) type,
(splay_tree_value) other_type);
return other_type;
}
/* Not compatible, look for next instance with same name. */
}
else
{
/* No more instances, create new one since this is the first
time we saw this type. */
brand->seq = i++;
/* Insert the new brand. */
splay_tree_insert (all_canon_types,
(splay_tree_key) brand,
(splay_tree_value) type);
/* Insert this new type as an alias for itself. */
splay_tree_insert (type_to_canon_type,
(splay_tree_key) type,
(splay_tree_value) type);
/* Insert the uid for reverse lookup; */
splay_tree_insert (uid_to_canon_type,
(splay_tree_key) TYPE_UID (type),
(splay_tree_value) type);
bitmap_set_bit (global_types_seen, TYPE_UID (type));
return type;
}
}
}
/* Return true if TYPE is one of the type classes that we are willing
to analyze. This skips the goofy types like arrays of pointers to
methods. */
static bool
type_to_consider (tree type)
{
/* Strip the *'s off. */
type = TYPE_MAIN_VARIANT (type);
while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE)
type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
switch (TREE_CODE (type))
{
case BOOLEAN_TYPE:
case COMPLEX_TYPE:
case ENUMERAL_TYPE:
case INTEGER_TYPE:
case QUAL_UNION_TYPE:
case REAL_TYPE:
case FIXED_POINT_TYPE:
case RECORD_TYPE:
case UNION_TYPE:
case VECTOR_TYPE:
case VOID_TYPE:
return true;
default:
return false;
}
}
/* Get the canon type of TYPE. If SEE_THRU_PTRS is true, remove all
the POINTER_TOs and if SEE_THRU_ARRAYS is true, remove all of the
ARRAY_OFs and POINTER_TOs. */
static tree
get_canon_type (tree type, bool see_thru_ptrs, bool see_thru_arrays)
{
splay_tree_node result;
/* Strip the *'s off. */
if (!type || !type_to_consider (type))
return NULL;
type = TYPE_MAIN_VARIANT (type);
if (see_thru_arrays)
while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE)
type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
else if (see_thru_ptrs)
while (POINTER_TYPE_P (type))
type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
result = splay_tree_lookup(type_to_canon_type, (splay_tree_key) type);
if (result == NULL)
return discover_unique_type (type);
else return (tree) result->value;
}
/* Same as GET_CANON_TYPE, except return the TYPE_ID rather than the
TYPE. */
static int
get_canon_type_uid (tree type, bool see_thru_ptrs, bool see_thru_arrays)
{
type = get_canon_type (type, see_thru_ptrs, see_thru_arrays);
if (type)
return TYPE_UID(type);
else return 0;
}
/* Return 0 if TYPE is a record or union type. Return a positive
number if TYPE is a pointer to a record or union. The number is
the number of pointer types stripped to get to the record or union
type. Return -1 if TYPE is none of the above. */
int
ipa_type_escape_star_count_of_interesting_type (tree type)
{
int count = 0;
/* Strip the *'s off. */
if (!type)
return -1;
type = TYPE_MAIN_VARIANT (type);
while (POINTER_TYPE_P (type))
{
type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
count++;
}
/* We are interested in records, and unions only. */
if (TREE_CODE (type) == RECORD_TYPE
|| TREE_CODE (type) == QUAL_UNION_TYPE
|| TREE_CODE (type) == UNION_TYPE)
return count;
else
return -1;
}
/* Return 0 if TYPE is a record or union type. Return a positive
number if TYPE is a pointer to a record or union. The number is
the number of pointer types stripped to get to the record or union
type. Return -1 if TYPE is none of the above. */
int
ipa_type_escape_star_count_of_interesting_or_array_type (tree type)
{
int count = 0;
/* Strip the *'s off. */
if (!type)
return -1;
type = TYPE_MAIN_VARIANT (type);
while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE)
{
type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
count++;
}
/* We are interested in records, and unions only. */
if (TREE_CODE (type) == RECORD_TYPE
|| TREE_CODE (type) == QUAL_UNION_TYPE
|| TREE_CODE (type) == UNION_TYPE)
return count;
else
return -1;
}
/* Return true if the record, or union TYPE passed in escapes this
compilation unit. Note that all of the pointer-to's are removed
before testing since these may not be correct. */
bool
ipa_type_escape_type_contained_p (tree type)
{
if (!initialized)
return false;
return !bitmap_bit_p (global_types_full_escape,
get_canon_type_uid (type, true, false));
}
/* Return true if a modification to a field of type FIELD_TYPE cannot
clobber a record of RECORD_TYPE. */
bool
ipa_type_escape_field_does_not_clobber_p (tree record_type, tree field_type)
{
splay_tree_node result;
int uid;
if (!initialized)
return false;
/* Strip off all of the pointer tos on the record type. Strip the
same number of pointer tos from the field type. If the field
type has fewer, it could not have been aliased. */
record_type = TYPE_MAIN_VARIANT (record_type);
field_type = TYPE_MAIN_VARIANT (field_type);
while (POINTER_TYPE_P (record_type))
{
record_type = TYPE_MAIN_VARIANT (TREE_TYPE (record_type));
if (POINTER_TYPE_P (field_type))
field_type = TYPE_MAIN_VARIANT (TREE_TYPE (field_type));
else
/* However, if field_type is a union, this quick test is not
correct since one of the variants of the union may be a
pointer to type and we cannot see across that here. So we
just strip the remaining pointer tos off the record type
and fall thru to the more precise code. */
if (TREE_CODE (field_type) == QUAL_UNION_TYPE
|| TREE_CODE (field_type) == UNION_TYPE)
{
while (POINTER_TYPE_P (record_type))
record_type = TYPE_MAIN_VARIANT (TREE_TYPE (record_type));
break;
}
else
return true;
}
record_type = get_canon_type (record_type, true, true);
/* The record type must be contained. The field type may
escape. */
if (!ipa_type_escape_type_contained_p (record_type))
return false;
uid = TYPE_UID (record_type);
result = splay_tree_lookup (uid_to_addressof_down_map, (splay_tree_key) uid);
if (result)
{
bitmap field_type_map = (bitmap) result->value;
uid = get_canon_type_uid (field_type, true, true);
/* If the bit is there, the address was taken. If not, it
wasn't. */
return !bitmap_bit_p (field_type_map, uid);
}
else
/* No bitmap means no addresses were taken. */
return true;
}
/* Add TYPE to the suspect type set. Return true if the bit needed to
be marked. */
static tree
mark_type (tree type, enum escape_t escape_status)
{
bitmap map = NULL;
int uid;
type = get_canon_type (type, true, true);
if (!type)
return NULL;
switch (escape_status)
{
case EXPOSED_PARAMETER:
map = global_types_exposed_parameter;
break;
case FULL_ESCAPE:
map = global_types_full_escape;
break;
}
uid = TYPE_UID (type);
if (bitmap_bit_p (map, uid))
return type;
else
{
bitmap_set_bit (map, uid);
if (escape_status == FULL_ESCAPE)
{
/* Efficiency hack. When things are bad, do not mess around
with this type anymore. */
bitmap_set_bit (global_types_exposed_parameter, uid);
}
}
return type;
}
/* Add interesting TYPE to the suspect type set. If the set is
EXPOSED_PARAMETER and the TYPE is a pointer type, the set is
changed to FULL_ESCAPE. */
static void
mark_interesting_type (tree type, enum escape_t escape_status)
{
if (!type) return;
if (ipa_type_escape_star_count_of_interesting_type (type) >= 0)
{
if ((escape_status == EXPOSED_PARAMETER)
&& POINTER_TYPE_P (type))
/* EXPOSED_PARAMETERs are only structs or unions are passed by
value. Anything passed by reference to an external
function fully exposes the type. */
mark_type (type, FULL_ESCAPE);
else
mark_type (type, escape_status);
}
}
/* Return true if PARENT is supertype of CHILD. Both types must be
known to be structures or unions. */
static bool
parent_type_p (tree parent, tree child)
{
int i;
tree binfo, base_binfo;
if (TYPE_BINFO (parent))
for (binfo = TYPE_BINFO (parent), i = 0;
BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
{
tree binfotype = BINFO_TYPE (base_binfo);
if (binfotype == child)
return true;
else if (parent_type_p (binfotype, child))
return true;
}
if (TREE_CODE (parent) == UNION_TYPE
|| TREE_CODE (parent) == QUAL_UNION_TYPE)
{
tree field;
/* Search all of the variants in the union to see if one of them
is the child. */
for (field = TYPE_FIELDS (parent);
field;
field = TREE_CHAIN (field))
{
tree field_type;
if (TREE_CODE (field) != FIELD_DECL)
continue;
field_type = TREE_TYPE (field);
if (field_type == child)
return true;
}
/* If we did not find it, recursively ask the variants if one of
their children is the child type. */
for (field = TYPE_FIELDS (parent);
field;
field = TREE_CHAIN (field))
{
tree field_type;
if (TREE_CODE (field) != FIELD_DECL)
continue;
field_type = TREE_TYPE (field);
if (TREE_CODE (field_type) == RECORD_TYPE
|| TREE_CODE (field_type) == QUAL_UNION_TYPE
|| TREE_CODE (field_type) == UNION_TYPE)
if (parent_type_p (field_type, child))
return true;
}
}
if (TREE_CODE (parent) == RECORD_TYPE)
{
tree field;
for (field = TYPE_FIELDS (parent);
field;
field = TREE_CHAIN (field))
{
tree field_type;
if (TREE_CODE (field) != FIELD_DECL)
continue;
field_type = TREE_TYPE (field);
if (field_type == child)
return true;
/* You can only cast to the first field so if it does not
match, quit. */
if (TREE_CODE (field_type) == RECORD_TYPE
|| TREE_CODE (field_type) == QUAL_UNION_TYPE
|| TREE_CODE (field_type) == UNION_TYPE)
{
if (parent_type_p (field_type, child))
return true;
else
break;
}
}
}
return false;
}
/* Return the number of pointer tos for TYPE and return TYPE with all
of these stripped off. */
static int
count_stars (tree* type_ptr)
{
tree type = *type_ptr;
int i = 0;
type = TYPE_MAIN_VARIANT (type);
while (POINTER_TYPE_P (type))
{
type = TYPE_MAIN_VARIANT (TREE_TYPE (type));
i++;
}
*type_ptr = type;
return i;
}
enum cast_type {
CT_UP = 0x1,
CT_DOWN = 0x2,
CT_SIDEWAYS = 0x4,
CT_USELESS = 0x8,
CT_FROM_P_BAD = 0x10,
CT_FROM_NON_P = 0x20,
CT_TO_NON_INTER = 0x40,
CT_FROM_MALLOC = 0x80,
CT_NO_CAST = 0x100
};
/* Check the cast FROM_TYPE to TO_TYPE. This function requires that
the two types have already passed the
ipa_type_escape_star_count_of_interesting_type test. */
static enum cast_type
check_cast_type (tree to_type, tree from_type)
{
int to_stars = count_stars (&to_type);
int from_stars = count_stars (&from_type);
if (to_stars != from_stars)
return CT_SIDEWAYS;
if (to_type == from_type)
return CT_USELESS;
if (parent_type_p (to_type, from_type)) return CT_UP;
if (parent_type_p (from_type, to_type)) return CT_DOWN;
return CT_SIDEWAYS;
}
/* This function returns nonzero if VAR is result of call
to malloc function. */
static bool
is_malloc_result (tree var)
{
tree def_stmt;
tree rhs;
int flags;
if (!var)
return false;
if (SSA_NAME_IS_DEFAULT_DEF (var))
return false;
def_stmt = SSA_NAME_DEF_STMT (var);
if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT)
return false;
if (var != GIMPLE_STMT_OPERAND (def_stmt, 0))
return false;
rhs = get_call_expr_in (def_stmt);
if (!rhs)
return false;
flags = call_expr_flags (rhs);
return ((flags & ECF_MALLOC) != 0);
}
/* Check a cast FROM this variable, TO_TYPE. Mark the escaping types
if appropriate. Returns cast_type as detected. */
static enum cast_type
check_cast (tree to_type, tree from)
{
tree from_type = get_canon_type (TREE_TYPE (from), false, false);
bool to_interesting_type, from_interesting_type;
enum cast_type cast = CT_NO_CAST;
to_type = get_canon_type (to_type, false, false);
if (!from_type || !to_type || from_type == to_type)
return cast;
to_interesting_type =
ipa_type_escape_star_count_of_interesting_type (to_type) >= 0;
from_interesting_type =
ipa_type_escape_star_count_of_interesting_type (from_type) >= 0;
if (to_interesting_type)
if (from_interesting_type)
{
/* Both types are interesting. This can be one of four types
of cast: useless, up, down, or sideways. We do not care
about up or useless. Sideways casts are always bad and
both sides get marked as escaping. Downcasts are not
interesting here because if type is marked as escaping, all
of its subtypes escape. */
cast = check_cast_type (to_type, from_type);
switch (cast)
{
case CT_UP:
case CT_USELESS:
case CT_DOWN:
break;
case CT_SIDEWAYS:
mark_type (to_type, FULL_ESCAPE);
mark_type (from_type, FULL_ESCAPE);
break;
default:
break;
}
}
else
{
/* This code excludes two cases from marking as escaped:
1. if this is a cast of index of array of structures/unions
that happens before accessing array element, we should not
mark it as escaped.
2. if this is a cast from the local that is a result from a
call to malloc, do not mark the cast as bad.
*/
if (POINTER_TYPE_P (to_type) && !POINTER_TYPE_P (from_type))
cast = CT_FROM_NON_P;
else if (TREE_CODE (from) == SSA_NAME
&& is_malloc_result (from))
cast = CT_FROM_MALLOC;
else
{
cast = CT_FROM_P_BAD;
mark_type (to_type, FULL_ESCAPE);
}
}
else if (from_interesting_type)
{
mark_type (from_type, FULL_ESCAPE);
cast = CT_TO_NON_INTER;
}
return cast;
}
typedef struct cast
{
int type;
tree stmt;
}cast_t;
/* This function is a callback for walk_tree called from
is_cast_from_non_pointer. The data->type is set to be:
0 - if there is no cast
number - the number of casts from non-pointer type
-1 - if there is a cast that makes the type to escape
If data->type = number, then data->stmt will contain the
last casting stmt met in traversing. */
static tree
is_cast_from_non_pointer_1 (tree *tp, int *walk_subtrees, void *data)
{
tree def_stmt = *tp;
if (pointer_set_insert (visited_stmts, def_stmt))
{
*walk_subtrees = 0;
return NULL;
}
switch (TREE_CODE (def_stmt))
{
case GIMPLE_MODIFY_STMT:
{
use_operand_p use_p;
ssa_op_iter iter;
tree lhs = GIMPLE_STMT_OPERAND (def_stmt, 0);
tree rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
unsigned int cast = look_for_casts (lhs, rhs);
/* Check that only one cast happened, and it's of
non-pointer type. */
if ((cast & CT_FROM_NON_P) == (CT_FROM_NON_P)
&& (cast & ~(CT_FROM_NON_P)) == 0)
{
((cast_t *)data)->stmt = def_stmt;
((cast_t *)data)->type++;
FOR_EACH_SSA_USE_OPERAND (use_p, def_stmt, iter, SSA_OP_ALL_USES)
{
walk_use_def_chains (USE_FROM_PTR (use_p), is_cast_from_non_pointer,
data, false);
if (((cast_t*)data)->type == -1)
return def_stmt;
}
}
/* Check that there is no cast, or cast is not harmful. */
else if ((cast & CT_NO_CAST) == (CT_NO_CAST)
|| (cast & CT_DOWN) == (CT_DOWN)
|| (cast & CT_UP) == (CT_UP)
|| (cast & CT_USELESS) == (CT_USELESS)
|| (cast & CT_FROM_MALLOC) == (CT_FROM_MALLOC))
{
FOR_EACH_SSA_USE_OPERAND (use_p, def_stmt, iter, SSA_OP_ALL_USES)
{
walk_use_def_chains (USE_FROM_PTR (use_p), is_cast_from_non_pointer,
data, false);
if (((cast_t*)data)->type == -1)
return def_stmt;
}
}
/* The cast is harmful. */
else
{
((cast_t *)data)->type = -1;
return def_stmt;
}
*walk_subtrees = 0;
}
break;
default:
{
*walk_subtrees = 0;
break;
}
}
return NULL;
}
/* This function is a callback for walk_use_def_chains function called
from is_array_access_through_pointer_and_index. */
static bool
is_cast_from_non_pointer (tree var, tree def_stmt, void *data)
{
if (!def_stmt || !var)
return false;
if (TREE_CODE (def_stmt) == PHI_NODE)
return false;
if (SSA_NAME_IS_DEFAULT_DEF (var))
return false;
walk_tree (&def_stmt, is_cast_from_non_pointer_1, data, NULL);
if (((cast_t*)data)->type == -1)
return true;
return false;
}
/* When array element a_p[i] is accessed through the pointer a_p
and index i, it's translated into the following sequence
in gimple:
i.1_5 = (unsigned int) i_1;
D.1605_6 = i.1_5 * 16;
D.1606_7 = (struct str_t *) D.1605_6;
a_p.2_8 = a_p;
D.1608_9 = D.1606_7 + a_p.2_8;
OP0 and OP1 are of the same pointer types and stand for
D.1606_7 and a_p.2_8 or vise versa.
This function checks that:
1. one of OP0 and OP1 (D.1606_7) has passed only one cast from
non-pointer type (D.1606_7 = (struct str_t *) D.1605_6;).
2. one of OP0 and OP1 which has passed the cast from
non-pointer type (D.1606_7), is actually generated by multiplication of
index by size of type to which both OP0 and OP1 point to
(in this case D.1605_6 = i.1_5 * 16; ).
3. an address of def of the var to which was made cast (D.1605_6)
was not taken.(How can it happen?)
The following items are checked implicitly by the end of algorithm:
4. one of OP0 and OP1 (a_p.2_8) have never been cast
(because if it was cast to pointer type, its type, that is also
the type of OP0 and OP1, will be marked as escaped during
analysis of casting stmt (when check_cast() is called
from scan_for_refs for this stmt)).
5. defs of OP0 and OP1 are not passed into externally visible function
(because if they are passed then their type, that is also the type of OP0
and OP1, will be marked and escaped during check_call function called from
scan_for_refs with call stmt).
In total, 1-5 guaranty that it's an access to array by pointer and index.
*/
bool
is_array_access_through_pointer_and_index (enum tree_code code, tree op0,
tree op1, tree *base, tree *offset,
tree *offset_cast_stmt)
{
tree before_cast, before_cast_def_stmt;
cast_t op0_cast, op1_cast;
*base = NULL;
*offset = NULL;
*offset_cast_stmt = NULL;
/* Check 1. */
if (code == POINTER_PLUS_EXPR)
{
tree op0type = TYPE_MAIN_VARIANT (TREE_TYPE (op0));
tree op1type = TYPE_MAIN_VARIANT (TREE_TYPE (op1));
/* One of op0 and op1 is of pointer type and the other is numerical. */
if (POINTER_TYPE_P (op0type) && NUMERICAL_TYPE_CHECK (op1type))
{
*base = op0;
*offset = op1;
}
else if (POINTER_TYPE_P (op1type) && NUMERICAL_TYPE_CHECK (op0type))
{
*base = op1;
*offset = op0;
}
else
return false;
}
else
{
/* Init data for walk_use_def_chains function. */
op0_cast.type = op1_cast.type = 0;
op0_cast.stmt = op1_cast.stmt = NULL;
visited_stmts = pointer_set_create ();
walk_use_def_chains (op0, is_cast_from_non_pointer,(void *)(&op0_cast),
false);
pointer_set_destroy (visited_stmts);
visited_stmts = pointer_set_create ();
walk_use_def_chains (op1, is_cast_from_non_pointer,(void *)(&op1_cast),
false);
pointer_set_destroy (visited_stmts);
if (op0_cast.type == 1 && op1_cast.type == 0)
{
*base = op1;
*offset = op0;
*offset_cast_stmt = op0_cast.stmt;
}
else if (op0_cast.type == 0 && op1_cast.type == 1)
{
*base = op0;
*offset = op1;
*offset_cast_stmt = op1_cast.stmt;
}
else
return false;
}
/* Check 2.
offset_cast_stmt is of the form:
D.1606_7 = (struct str_t *) D.1605_6; */
if (*offset_cast_stmt)
{
before_cast = SINGLE_SSA_TREE_OPERAND (*offset_cast_stmt, SSA_OP_USE);
if (!before_cast)