111
|
1 /* Interprocedural Identical Code Folding pass
|
131
|
2 Copyright (C) 2014-2018 Free Software Foundation, Inc.
|
111
|
3
|
|
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
|
|
5
|
|
6 This file is part of GCC.
|
|
7
|
|
8 GCC is free software; you can redistribute it and/or modify it under
|
|
9 the terms of the GNU General Public License as published by the Free
|
|
10 Software Foundation; either version 3, or (at your option) any later
|
|
11 version.
|
|
12
|
|
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
16 for more details.
|
|
17
|
|
18 You should have received a copy of the GNU General Public License
|
|
19 along with GCC; see the file COPYING3. If not see
|
|
20 <http://www.gnu.org/licenses/>. */
|
|
21
|
|
22 #include "config.h"
|
|
23 #include "system.h"
|
|
24 #include "coretypes.h"
|
|
25 #include "backend.h"
|
|
26 #include "rtl.h"
|
|
27 #include "tree.h"
|
|
28 #include "gimple.h"
|
|
29 #include "tree-pass.h"
|
|
30 #include "ssa.h"
|
|
31 #include "cgraph.h"
|
|
32 #include "data-streamer.h"
|
|
33 #include "gimple-pretty-print.h"
|
|
34 #include "alias.h"
|
|
35 #include "fold-const.h"
|
|
36 #include "gimple-iterator.h"
|
|
37 #include "ipa-utils.h"
|
|
38 #include "tree-eh.h"
|
|
39 #include "builtins.h"
|
|
40
|
|
41 #include "ipa-icf-gimple.h"
|
|
42
|
|
43 namespace ipa_icf_gimple {
|
|
44
|
|
45 /* Initialize internal structures for a given SOURCE_FUNC_DECL and
|
|
46 TARGET_FUNC_DECL. Strict polymorphic comparison is processed if
|
|
47 an option COMPARE_POLYMORPHIC is true. For special cases, one can
|
|
48 set IGNORE_LABELS to skip label comparison.
|
|
49 Similarly, IGNORE_SOURCE_DECLS and IGNORE_TARGET_DECLS are sets
|
|
50 of declarations that can be skipped. */
|
|
51
|
|
52 func_checker::func_checker (tree source_func_decl, tree target_func_decl,
|
|
53 bool compare_polymorphic,
|
|
54 bool ignore_labels,
|
|
55 hash_set<symtab_node *> *ignored_source_nodes,
|
|
56 hash_set<symtab_node *> *ignored_target_nodes)
|
|
57 : m_source_func_decl (source_func_decl), m_target_func_decl (target_func_decl),
|
|
58 m_ignored_source_nodes (ignored_source_nodes),
|
|
59 m_ignored_target_nodes (ignored_target_nodes),
|
|
60 m_compare_polymorphic (compare_polymorphic),
|
|
61 m_ignore_labels (ignore_labels)
|
|
62 {
|
|
63 function *source_func = DECL_STRUCT_FUNCTION (source_func_decl);
|
|
64 function *target_func = DECL_STRUCT_FUNCTION (target_func_decl);
|
|
65
|
|
66 unsigned ssa_source = SSANAMES (source_func)->length ();
|
|
67 unsigned ssa_target = SSANAMES (target_func)->length ();
|
|
68
|
|
69 m_source_ssa_names.create (ssa_source);
|
|
70 m_target_ssa_names.create (ssa_target);
|
|
71
|
|
72 for (unsigned i = 0; i < ssa_source; i++)
|
|
73 m_source_ssa_names.safe_push (-1);
|
|
74
|
|
75 for (unsigned i = 0; i < ssa_target; i++)
|
|
76 m_target_ssa_names.safe_push (-1);
|
|
77 }
|
|
78
|
|
79 /* Memory release routine. */
|
|
80
|
|
81 func_checker::~func_checker ()
|
|
82 {
|
|
83 m_source_ssa_names.release();
|
|
84 m_target_ssa_names.release();
|
|
85 }
|
|
86
|
|
87 /* Verifies that trees T1 and T2 are equivalent from perspective of ICF. */
|
|
88
|
|
89 bool
|
|
90 func_checker::compare_ssa_name (tree t1, tree t2)
|
|
91 {
|
|
92 gcc_assert (TREE_CODE (t1) == SSA_NAME);
|
|
93 gcc_assert (TREE_CODE (t2) == SSA_NAME);
|
|
94
|
|
95 unsigned i1 = SSA_NAME_VERSION (t1);
|
|
96 unsigned i2 = SSA_NAME_VERSION (t2);
|
|
97
|
|
98 if (m_source_ssa_names[i1] == -1)
|
|
99 m_source_ssa_names[i1] = i2;
|
|
100 else if (m_source_ssa_names[i1] != (int) i2)
|
|
101 return false;
|
|
102
|
|
103 if(m_target_ssa_names[i2] == -1)
|
|
104 m_target_ssa_names[i2] = i1;
|
|
105 else if (m_target_ssa_names[i2] != (int) i1)
|
|
106 return false;
|
|
107
|
|
108 if (SSA_NAME_IS_DEFAULT_DEF (t1))
|
|
109 {
|
|
110 tree b1 = SSA_NAME_VAR (t1);
|
|
111 tree b2 = SSA_NAME_VAR (t2);
|
|
112
|
|
113 if (b1 == NULL && b2 == NULL)
|
|
114 return true;
|
|
115
|
|
116 if (b1 == NULL || b2 == NULL || TREE_CODE (b1) != TREE_CODE (b2))
|
|
117 return return_false ();
|
|
118
|
|
119 return compare_cst_or_decl (b1, b2);
|
|
120 }
|
|
121
|
|
122 return true;
|
|
123 }
|
|
124
|
|
125 /* Verification function for edges E1 and E2. */
|
|
126
|
|
127 bool
|
|
128 func_checker::compare_edge (edge e1, edge e2)
|
|
129 {
|
|
130 if (e1->flags != e2->flags)
|
|
131 return false;
|
|
132
|
|
133 bool existed_p;
|
|
134
|
|
135 edge &slot = m_edge_map.get_or_insert (e1, &existed_p);
|
|
136 if (existed_p)
|
|
137 return return_with_debug (slot == e2);
|
|
138 else
|
|
139 slot = e2;
|
|
140
|
|
141 /* TODO: filter edge probabilities for profile feedback match. */
|
|
142
|
|
143 return true;
|
|
144 }
|
|
145
|
|
146 /* Verification function for declaration trees T1 and T2 that
|
|
147 come from functions FUNC1 and FUNC2. */
|
|
148
|
|
149 bool
|
|
150 func_checker::compare_decl (tree t1, tree t2)
|
|
151 {
|
|
152 if (!auto_var_in_fn_p (t1, m_source_func_decl)
|
|
153 || !auto_var_in_fn_p (t2, m_target_func_decl))
|
|
154 return return_with_debug (t1 == t2);
|
|
155
|
|
156 tree_code t = TREE_CODE (t1);
|
|
157 if ((t == VAR_DECL || t == PARM_DECL || t == RESULT_DECL)
|
|
158 && DECL_BY_REFERENCE (t1) != DECL_BY_REFERENCE (t2))
|
|
159 return return_false_with_msg ("DECL_BY_REFERENCE flags are different");
|
|
160
|
|
161 if (!compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
|
|
162 return return_false ();
|
|
163
|
|
164 /* TODO: we are actually too strict here. We only need to compare if
|
|
165 T1 can be used in polymorphic call. */
|
|
166 if (TREE_ADDRESSABLE (t1)
|
|
167 && m_compare_polymorphic
|
|
168 && !compatible_polymorphic_types_p (TREE_TYPE (t1), TREE_TYPE (t2),
|
|
169 false))
|
|
170 return return_false ();
|
|
171
|
|
172 if ((t == VAR_DECL || t == PARM_DECL || t == RESULT_DECL)
|
|
173 && DECL_BY_REFERENCE (t1)
|
|
174 && m_compare_polymorphic
|
|
175 && !compatible_polymorphic_types_p (TREE_TYPE (t1), TREE_TYPE (t2),
|
|
176 true))
|
|
177 return return_false ();
|
|
178
|
|
179 bool existed_p;
|
|
180
|
|
181 tree &slot = m_decl_map.get_or_insert (t1, &existed_p);
|
|
182 if (existed_p)
|
|
183 return return_with_debug (slot == t2);
|
|
184 else
|
|
185 slot = t2;
|
|
186
|
|
187 return true;
|
|
188 }
|
|
189
|
|
190 /* Return true if T1 and T2 are same for purposes of ipa-polymorphic-call
|
|
191 analysis. COMPARE_PTR indicates if types of pointers needs to be
|
|
192 considered. */
|
|
193
|
|
194 bool
|
|
195 func_checker::compatible_polymorphic_types_p (tree t1, tree t2,
|
|
196 bool compare_ptr)
|
|
197 {
|
|
198 gcc_assert (TREE_CODE (t1) != FUNCTION_TYPE && TREE_CODE (t1) != METHOD_TYPE);
|
|
199
|
|
200 /* Pointer types generally give no information. */
|
|
201 if (POINTER_TYPE_P (t1))
|
|
202 {
|
|
203 if (!compare_ptr)
|
|
204 return true;
|
|
205 return func_checker::compatible_polymorphic_types_p (TREE_TYPE (t1),
|
|
206 TREE_TYPE (t2),
|
|
207 false);
|
|
208 }
|
|
209
|
|
210 /* If types contain a polymorphic types, match them. */
|
|
211 bool c1 = contains_polymorphic_type_p (t1);
|
|
212 bool c2 = contains_polymorphic_type_p (t2);
|
|
213 if (!c1 && !c2)
|
|
214 return true;
|
|
215 if (!c1 || !c2)
|
|
216 return return_false_with_msg ("one type is not polymorphic");
|
|
217 if (!types_must_be_same_for_odr (t1, t2))
|
|
218 return return_false_with_msg ("types are not same for ODR");
|
|
219 return true;
|
|
220 }
|
|
221
|
|
222 /* Return true if types are compatible from perspective of ICF. */
|
|
223 bool
|
|
224 func_checker::compatible_types_p (tree t1, tree t2)
|
|
225 {
|
|
226 if (TREE_CODE (t1) != TREE_CODE (t2))
|
|
227 return return_false_with_msg ("different tree types");
|
|
228
|
|
229 if (TYPE_RESTRICT (t1) != TYPE_RESTRICT (t2))
|
|
230 return return_false_with_msg ("restrict flags are different");
|
|
231
|
|
232 if (!types_compatible_p (t1, t2))
|
|
233 return return_false_with_msg ("types are not compatible");
|
|
234
|
|
235 /* We do a lot of unnecesary matching of types that are not being
|
|
236 accessed and thus do not need to be compatible. In longer term we should
|
|
237 remove these checks on all types which are not accessed as memory
|
|
238 locations.
|
|
239
|
|
240 For time being just avoid calling get_alias_set on types that are not
|
|
241 having alias sets defined at all. */
|
|
242 if (type_with_alias_set_p (t1) && type_with_alias_set_p (t2)
|
|
243 && get_alias_set (t1) != get_alias_set (t2))
|
|
244 return return_false_with_msg ("alias sets are different");
|
|
245
|
|
246 return true;
|
|
247 }
|
|
248
|
|
249 /* Function compare for equality given memory operands T1 and T2. */
|
|
250
|
|
251 bool
|
|
252 func_checker::compare_memory_operand (tree t1, tree t2)
|
|
253 {
|
|
254 if (!t1 && !t2)
|
|
255 return true;
|
|
256 else if (!t1 || !t2)
|
|
257 return false;
|
|
258
|
|
259 ao_ref r1, r2;
|
|
260 ao_ref_init (&r1, t1);
|
|
261 ao_ref_init (&r2, t2);
|
|
262
|
|
263 tree b1 = ao_ref_base (&r1);
|
|
264 tree b2 = ao_ref_base (&r2);
|
|
265
|
|
266 bool source_is_memop = DECL_P (b1) || INDIRECT_REF_P (b1)
|
|
267 || TREE_CODE (b1) == MEM_REF
|
|
268 || TREE_CODE (b1) == TARGET_MEM_REF;
|
|
269
|
|
270 bool target_is_memop = DECL_P (b2) || INDIRECT_REF_P (b2)
|
|
271 || TREE_CODE (b2) == MEM_REF
|
|
272 || TREE_CODE (b2) == TARGET_MEM_REF;
|
|
273
|
|
274 /* Compare alias sets for memory operands. */
|
|
275 if (source_is_memop && target_is_memop)
|
|
276 {
|
|
277 if (TREE_THIS_VOLATILE (t1) != TREE_THIS_VOLATILE (t2))
|
|
278 return return_false_with_msg ("different operand volatility");
|
|
279
|
|
280 if (ao_ref_alias_set (&r1) != ao_ref_alias_set (&r2)
|
|
281 || ao_ref_base_alias_set (&r1) != ao_ref_base_alias_set (&r2))
|
|
282 return return_false_with_msg ("ao alias sets are different");
|
|
283
|
|
284 /* We can't simply use get_object_alignment_1 on the full
|
|
285 reference as for accesses with variable indexes this reports
|
|
286 too conservative alignment. We also can't use the ao_ref_base
|
|
287 base objects as ao_ref_base happily strips MEM_REFs around
|
|
288 decls even though that may carry alignment info. */
|
|
289 b1 = t1;
|
|
290 while (handled_component_p (b1))
|
|
291 b1 = TREE_OPERAND (b1, 0);
|
|
292 b2 = t2;
|
|
293 while (handled_component_p (b2))
|
|
294 b2 = TREE_OPERAND (b2, 0);
|
|
295 unsigned int align1, align2;
|
|
296 unsigned HOST_WIDE_INT tem;
|
|
297 get_object_alignment_1 (b1, &align1, &tem);
|
|
298 get_object_alignment_1 (b2, &align2, &tem);
|
|
299 if (align1 != align2)
|
|
300 return return_false_with_msg ("different access alignment");
|
|
301
|
|
302 /* Similarly we have to compare dependence info where equality
|
|
303 tells us we are safe (even some unequal values would be safe
|
|
304 but then we have to maintain a map of bases and cliques). */
|
|
305 unsigned short clique1 = 0, base1 = 0, clique2 = 0, base2 = 0;
|
|
306 if (TREE_CODE (b1) == MEM_REF)
|
|
307 {
|
|
308 clique1 = MR_DEPENDENCE_CLIQUE (b1);
|
|
309 base1 = MR_DEPENDENCE_BASE (b1);
|
|
310 }
|
|
311 if (TREE_CODE (b2) == MEM_REF)
|
|
312 {
|
|
313 clique2 = MR_DEPENDENCE_CLIQUE (b2);
|
|
314 base2 = MR_DEPENDENCE_BASE (b2);
|
|
315 }
|
|
316 if (clique1 != clique2 || base1 != base2)
|
|
317 return return_false_with_msg ("different dependence info");
|
|
318 }
|
|
319
|
|
320 return compare_operand (t1, t2);
|
|
321 }
|
|
322
|
|
323 /* Function compare for equality given trees T1 and T2 which
|
|
324 can be either a constant or a declaration type. */
|
|
325
|
|
326 bool
|
|
327 func_checker::compare_cst_or_decl (tree t1, tree t2)
|
|
328 {
|
|
329 bool ret;
|
|
330
|
|
331 switch (TREE_CODE (t1))
|
|
332 {
|
|
333 case INTEGER_CST:
|
|
334 case COMPLEX_CST:
|
|
335 case VECTOR_CST:
|
|
336 case STRING_CST:
|
|
337 case REAL_CST:
|
|
338 {
|
|
339 ret = compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2))
|
|
340 && operand_equal_p (t1, t2, OEP_ONLY_CONST);
|
|
341 return return_with_debug (ret);
|
|
342 }
|
|
343 case FUNCTION_DECL:
|
|
344 /* All function decls are in the symbol table and known to match
|
|
345 before we start comparing bodies. */
|
|
346 return true;
|
|
347 case VAR_DECL:
|
|
348 return return_with_debug (compare_variable_decl (t1, t2));
|
|
349 case FIELD_DECL:
|
|
350 {
|
|
351 tree offset1 = DECL_FIELD_OFFSET (t1);
|
|
352 tree offset2 = DECL_FIELD_OFFSET (t2);
|
|
353
|
|
354 tree bit_offset1 = DECL_FIELD_BIT_OFFSET (t1);
|
|
355 tree bit_offset2 = DECL_FIELD_BIT_OFFSET (t2);
|
|
356
|
|
357 ret = compare_operand (offset1, offset2)
|
|
358 && compare_operand (bit_offset1, bit_offset2);
|
|
359
|
|
360 return return_with_debug (ret);
|
|
361 }
|
|
362 case LABEL_DECL:
|
|
363 {
|
|
364 if (t1 == t2)
|
|
365 return true;
|
|
366
|
|
367 int *bb1 = m_label_bb_map.get (t1);
|
|
368 int *bb2 = m_label_bb_map.get (t2);
|
|
369
|
|
370 /* Labels can point to another function (non-local GOTOs). */
|
|
371 return return_with_debug (bb1 != NULL && bb2 != NULL && *bb1 == *bb2);
|
|
372 }
|
|
373 case PARM_DECL:
|
|
374 case RESULT_DECL:
|
|
375 case CONST_DECL:
|
|
376 {
|
|
377 ret = compare_decl (t1, t2);
|
|
378 return return_with_debug (ret);
|
|
379 }
|
|
380 default:
|
|
381 gcc_unreachable ();
|
|
382 }
|
|
383 }
|
|
384
|
|
385 /* Function responsible for comparison of various operands T1 and T2.
|
|
386 If these components, from functions FUNC1 and FUNC2, are equal, true
|
|
387 is returned. */
|
|
388
|
|
389 bool
|
|
390 func_checker::compare_operand (tree t1, tree t2)
|
|
391 {
|
|
392 tree x1, x2, y1, y2, z1, z2;
|
|
393 bool ret;
|
|
394
|
|
395 if (!t1 && !t2)
|
|
396 return true;
|
|
397 else if (!t1 || !t2)
|
|
398 return false;
|
|
399
|
|
400 tree tt1 = TREE_TYPE (t1);
|
|
401 tree tt2 = TREE_TYPE (t2);
|
|
402
|
|
403 if (!func_checker::compatible_types_p (tt1, tt2))
|
|
404 return false;
|
|
405
|
|
406 if (TREE_CODE (t1) != TREE_CODE (t2))
|
|
407 return return_false ();
|
|
408
|
|
409 switch (TREE_CODE (t1))
|
|
410 {
|
|
411 case CONSTRUCTOR:
|
|
412 {
|
|
413 unsigned length1 = CONSTRUCTOR_NELTS (t1);
|
|
414 unsigned length2 = CONSTRUCTOR_NELTS (t2);
|
|
415
|
|
416 if (length1 != length2)
|
|
417 return return_false ();
|
|
418
|
|
419 for (unsigned i = 0; i < length1; i++)
|
|
420 if (!compare_operand (CONSTRUCTOR_ELT (t1, i)->value,
|
|
421 CONSTRUCTOR_ELT (t2, i)->value))
|
|
422 return return_false();
|
|
423
|
|
424 return true;
|
|
425 }
|
|
426 case ARRAY_REF:
|
|
427 case ARRAY_RANGE_REF:
|
|
428 /* First argument is the array, second is the index. */
|
|
429 x1 = TREE_OPERAND (t1, 0);
|
|
430 x2 = TREE_OPERAND (t2, 0);
|
|
431 y1 = TREE_OPERAND (t1, 1);
|
|
432 y2 = TREE_OPERAND (t2, 1);
|
|
433
|
|
434 if (!compare_operand (array_ref_low_bound (t1),
|
|
435 array_ref_low_bound (t2)))
|
|
436 return return_false_with_msg ("");
|
|
437 if (!compare_operand (array_ref_element_size (t1),
|
|
438 array_ref_element_size (t2)))
|
|
439 return return_false_with_msg ("");
|
|
440
|
|
441 if (!compare_operand (x1, x2))
|
|
442 return return_false_with_msg ("");
|
|
443 return compare_operand (y1, y2);
|
|
444 case MEM_REF:
|
|
445 {
|
|
446 x1 = TREE_OPERAND (t1, 0);
|
|
447 x2 = TREE_OPERAND (t2, 0);
|
|
448 y1 = TREE_OPERAND (t1, 1);
|
|
449 y2 = TREE_OPERAND (t2, 1);
|
|
450
|
|
451 /* See if operand is an memory access (the test originate from
|
|
452 gimple_load_p).
|
|
453
|
|
454 In this case the alias set of the function being replaced must
|
|
455 be subset of the alias set of the other function. At the moment
|
|
456 we seek for equivalency classes, so simply require inclussion in
|
|
457 both directions. */
|
|
458
|
|
459 if (!func_checker::compatible_types_p (TREE_TYPE (x1), TREE_TYPE (x2)))
|
|
460 return return_false ();
|
|
461
|
|
462 if (!compare_operand (x1, x2))
|
|
463 return return_false_with_msg ("");
|
|
464
|
|
465 /* Type of the offset on MEM_REF does not matter. */
|
131
|
466 return known_eq (wi::to_poly_offset (y1), wi::to_poly_offset (y2));
|
111
|
467 }
|
|
468 case COMPONENT_REF:
|
|
469 {
|
|
470 x1 = TREE_OPERAND (t1, 0);
|
|
471 x2 = TREE_OPERAND (t2, 0);
|
|
472 y1 = TREE_OPERAND (t1, 1);
|
|
473 y2 = TREE_OPERAND (t2, 1);
|
|
474
|
|
475 ret = compare_operand (x1, x2)
|
|
476 && compare_cst_or_decl (y1, y2);
|
|
477
|
|
478 return return_with_debug (ret);
|
|
479 }
|
|
480 /* Virtual table call. */
|
|
481 case OBJ_TYPE_REF:
|
|
482 {
|
|
483 if (!compare_ssa_name (OBJ_TYPE_REF_EXPR (t1), OBJ_TYPE_REF_EXPR (t2)))
|
|
484 return return_false ();
|
|
485 if (opt_for_fn (m_source_func_decl, flag_devirtualize)
|
|
486 && virtual_method_call_p (t1))
|
|
487 {
|
|
488 if (tree_to_uhwi (OBJ_TYPE_REF_TOKEN (t1))
|
|
489 != tree_to_uhwi (OBJ_TYPE_REF_TOKEN (t2)))
|
|
490 return return_false_with_msg ("OBJ_TYPE_REF token mismatch");
|
|
491 if (!types_same_for_odr (obj_type_ref_class (t1),
|
|
492 obj_type_ref_class (t2)))
|
|
493 return return_false_with_msg ("OBJ_TYPE_REF OTR type mismatch");
|
|
494 if (!compare_operand (OBJ_TYPE_REF_OBJECT (t1),
|
|
495 OBJ_TYPE_REF_OBJECT (t2)))
|
|
496 return return_false_with_msg ("OBJ_TYPE_REF object mismatch");
|
|
497 }
|
|
498
|
|
499 return return_with_debug (true);
|
|
500 }
|
|
501 case IMAGPART_EXPR:
|
|
502 case REALPART_EXPR:
|
|
503 case ADDR_EXPR:
|
|
504 {
|
|
505 x1 = TREE_OPERAND (t1, 0);
|
|
506 x2 = TREE_OPERAND (t2, 0);
|
|
507
|
|
508 ret = compare_operand (x1, x2);
|
|
509 return return_with_debug (ret);
|
|
510 }
|
|
511 case BIT_FIELD_REF:
|
|
512 {
|
|
513 x1 = TREE_OPERAND (t1, 0);
|
|
514 x2 = TREE_OPERAND (t2, 0);
|
|
515 y1 = TREE_OPERAND (t1, 1);
|
|
516 y2 = TREE_OPERAND (t2, 1);
|
|
517 z1 = TREE_OPERAND (t1, 2);
|
|
518 z2 = TREE_OPERAND (t2, 2);
|
|
519
|
|
520 ret = compare_operand (x1, x2)
|
|
521 && compare_cst_or_decl (y1, y2)
|
|
522 && compare_cst_or_decl (z1, z2);
|
|
523
|
|
524 return return_with_debug (ret);
|
|
525 }
|
|
526 case SSA_NAME:
|
|
527 return compare_ssa_name (t1, t2);
|
|
528 case INTEGER_CST:
|
|
529 case COMPLEX_CST:
|
|
530 case VECTOR_CST:
|
|
531 case STRING_CST:
|
|
532 case REAL_CST:
|
|
533 case FUNCTION_DECL:
|
|
534 case VAR_DECL:
|
|
535 case FIELD_DECL:
|
|
536 case LABEL_DECL:
|
|
537 case PARM_DECL:
|
|
538 case RESULT_DECL:
|
|
539 case CONST_DECL:
|
|
540 return compare_cst_or_decl (t1, t2);
|
|
541 default:
|
|
542 return return_false_with_msg ("Unknown TREE code reached");
|
|
543 }
|
|
544 }
|
|
545
|
|
546 bool
|
|
547 func_checker::compare_asm_inputs_outputs (tree t1, tree t2)
|
|
548 {
|
|
549 gcc_assert (TREE_CODE (t1) == TREE_LIST);
|
|
550 gcc_assert (TREE_CODE (t2) == TREE_LIST);
|
|
551
|
|
552 for (; t1; t1 = TREE_CHAIN (t1))
|
|
553 {
|
|
554 if (!t2)
|
|
555 return false;
|
|
556
|
|
557 if (!compare_operand (TREE_VALUE (t1), TREE_VALUE (t2)))
|
|
558 return return_false ();
|
|
559
|
|
560 tree p1 = TREE_PURPOSE (t1);
|
|
561 tree p2 = TREE_PURPOSE (t2);
|
|
562
|
|
563 gcc_assert (TREE_CODE (p1) == TREE_LIST);
|
|
564 gcc_assert (TREE_CODE (p2) == TREE_LIST);
|
|
565
|
|
566 if (strcmp (TREE_STRING_POINTER (TREE_VALUE (p1)),
|
|
567 TREE_STRING_POINTER (TREE_VALUE (p2))) != 0)
|
|
568 return return_false ();
|
|
569
|
|
570 t2 = TREE_CHAIN (t2);
|
|
571 }
|
|
572
|
|
573 if (t2)
|
|
574 return return_false ();
|
|
575
|
|
576 return true;
|
|
577 }
|
|
578
|
|
579 /* Verifies that trees T1 and T2 do correspond. */
|
|
580
|
|
581 bool
|
|
582 func_checker::compare_variable_decl (tree t1, tree t2)
|
|
583 {
|
|
584 bool ret = false;
|
|
585
|
|
586 if (t1 == t2)
|
|
587 return true;
|
|
588
|
|
589 if (DECL_ALIGN (t1) != DECL_ALIGN (t2))
|
|
590 return return_false_with_msg ("alignments are different");
|
|
591
|
|
592 if (DECL_HARD_REGISTER (t1) != DECL_HARD_REGISTER (t2))
|
|
593 return return_false_with_msg ("DECL_HARD_REGISTER are different");
|
|
594
|
|
595 if (DECL_HARD_REGISTER (t1)
|
|
596 && DECL_ASSEMBLER_NAME (t1) != DECL_ASSEMBLER_NAME (t2))
|
|
597 return return_false_with_msg ("HARD REGISTERS are different");
|
|
598
|
|
599 /* Symbol table variables are known to match before we start comparing
|
|
600 bodies. */
|
|
601 if (decl_in_symtab_p (t1))
|
|
602 return decl_in_symtab_p (t2);
|
|
603 ret = compare_decl (t1, t2);
|
|
604
|
|
605 return return_with_debug (ret);
|
|
606 }
|
|
607
|
|
608
|
|
609 /* Function visits all gimple labels and creates corresponding
|
|
610 mapping between basic blocks and labels. */
|
|
611
|
|
612 void
|
|
613 func_checker::parse_labels (sem_bb *bb)
|
|
614 {
|
|
615 for (gimple_stmt_iterator gsi = gsi_start_bb (bb->bb); !gsi_end_p (gsi);
|
|
616 gsi_next (&gsi))
|
|
617 {
|
|
618 gimple *stmt = gsi_stmt (gsi);
|
|
619
|
|
620 if (glabel *label_stmt = dyn_cast <glabel *> (stmt))
|
|
621 {
|
|
622 tree t = gimple_label_label (label_stmt);
|
|
623 gcc_assert (TREE_CODE (t) == LABEL_DECL);
|
|
624
|
|
625 m_label_bb_map.put (t, bb->bb->index);
|
|
626 }
|
|
627 }
|
|
628 }
|
|
629
|
|
630 /* Basic block equivalence comparison function that returns true if
|
|
631 basic blocks BB1 and BB2 (from functions FUNC1 and FUNC2) correspond.
|
|
632
|
|
633 In general, a collection of equivalence dictionaries is built for types
|
|
634 like SSA names, declarations (VAR_DECL, PARM_DECL, ..). This infrastructure
|
|
635 is utilized by every statement-by-statement comparison function. */
|
|
636
|
|
637 bool
|
|
638 func_checker::compare_bb (sem_bb *bb1, sem_bb *bb2)
|
|
639 {
|
|
640 gimple_stmt_iterator gsi1, gsi2;
|
|
641 gimple *s1, *s2;
|
|
642
|
131
|
643 gsi1 = gsi_start_nondebug_bb (bb1->bb);
|
|
644 gsi2 = gsi_start_nondebug_bb (bb2->bb);
|
111
|
645
|
|
646 while (!gsi_end_p (gsi1))
|
|
647 {
|
|
648 if (gsi_end_p (gsi2))
|
|
649 return return_false ();
|
|
650
|
|
651 s1 = gsi_stmt (gsi1);
|
|
652 s2 = gsi_stmt (gsi2);
|
|
653
|
|
654 int eh1 = lookup_stmt_eh_lp_fn
|
|
655 (DECL_STRUCT_FUNCTION (m_source_func_decl), s1);
|
|
656 int eh2 = lookup_stmt_eh_lp_fn
|
|
657 (DECL_STRUCT_FUNCTION (m_target_func_decl), s2);
|
|
658
|
|
659 if (eh1 != eh2)
|
|
660 return return_false_with_msg ("EH regions are different");
|
|
661
|
|
662 if (gimple_code (s1) != gimple_code (s2))
|
|
663 return return_false_with_msg ("gimple codes are different");
|
|
664
|
|
665 switch (gimple_code (s1))
|
|
666 {
|
|
667 case GIMPLE_CALL:
|
|
668 if (!compare_gimple_call (as_a <gcall *> (s1),
|
|
669 as_a <gcall *> (s2)))
|
|
670 return return_different_stmts (s1, s2, "GIMPLE_CALL");
|
|
671 break;
|
|
672 case GIMPLE_ASSIGN:
|
|
673 if (!compare_gimple_assign (s1, s2))
|
|
674 return return_different_stmts (s1, s2, "GIMPLE_ASSIGN");
|
|
675 break;
|
|
676 case GIMPLE_COND:
|
|
677 if (!compare_gimple_cond (s1, s2))
|
|
678 return return_different_stmts (s1, s2, "GIMPLE_COND");
|
|
679 break;
|
|
680 case GIMPLE_SWITCH:
|
|
681 if (!compare_gimple_switch (as_a <gswitch *> (s1),
|
|
682 as_a <gswitch *> (s2)))
|
|
683 return return_different_stmts (s1, s2, "GIMPLE_SWITCH");
|
|
684 break;
|
|
685 case GIMPLE_DEBUG:
|
|
686 break;
|
|
687 case GIMPLE_EH_DISPATCH:
|
|
688 if (gimple_eh_dispatch_region (as_a <geh_dispatch *> (s1))
|
|
689 != gimple_eh_dispatch_region (as_a <geh_dispatch *> (s2)))
|
|
690 return return_different_stmts (s1, s2, "GIMPLE_EH_DISPATCH");
|
|
691 break;
|
|
692 case GIMPLE_RESX:
|
|
693 if (!compare_gimple_resx (as_a <gresx *> (s1),
|
|
694 as_a <gresx *> (s2)))
|
|
695 return return_different_stmts (s1, s2, "GIMPLE_RESX");
|
|
696 break;
|
|
697 case GIMPLE_LABEL:
|
|
698 if (!compare_gimple_label (as_a <glabel *> (s1),
|
|
699 as_a <glabel *> (s2)))
|
|
700 return return_different_stmts (s1, s2, "GIMPLE_LABEL");
|
|
701 break;
|
|
702 case GIMPLE_RETURN:
|
|
703 if (!compare_gimple_return (as_a <greturn *> (s1),
|
|
704 as_a <greturn *> (s2)))
|
|
705 return return_different_stmts (s1, s2, "GIMPLE_RETURN");
|
|
706 break;
|
|
707 case GIMPLE_GOTO:
|
|
708 if (!compare_gimple_goto (s1, s2))
|
|
709 return return_different_stmts (s1, s2, "GIMPLE_GOTO");
|
|
710 break;
|
|
711 case GIMPLE_ASM:
|
|
712 if (!compare_gimple_asm (as_a <gasm *> (s1),
|
|
713 as_a <gasm *> (s2)))
|
|
714 return return_different_stmts (s1, s2, "GIMPLE_ASM");
|
|
715 break;
|
|
716 case GIMPLE_PREDICT:
|
|
717 case GIMPLE_NOP:
|
|
718 break;
|
|
719 default:
|
|
720 return return_false_with_msg ("Unknown GIMPLE code reached");
|
|
721 }
|
|
722
|
|
723 gsi_next_nondebug (&gsi1);
|
|
724 gsi_next_nondebug (&gsi2);
|
|
725 }
|
|
726
|
|
727 if (!gsi_end_p (gsi2))
|
|
728 return return_false ();
|
|
729
|
|
730 return true;
|
|
731 }
|
|
732
|
|
733 /* Verifies for given GIMPLEs S1 and S2 that
|
|
734 call statements are semantically equivalent. */
|
|
735
|
|
736 bool
|
|
737 func_checker::compare_gimple_call (gcall *s1, gcall *s2)
|
|
738 {
|
|
739 unsigned i;
|
|
740 tree t1, t2;
|
|
741
|
|
742 if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
|
|
743 return false;
|
|
744
|
|
745 t1 = gimple_call_fn (s1);
|
|
746 t2 = gimple_call_fn (s2);
|
|
747 if (!compare_operand (t1, t2))
|
|
748 return return_false ();
|
|
749
|
|
750 /* Compare flags. */
|
|
751 if (gimple_call_internal_p (s1) != gimple_call_internal_p (s2)
|
|
752 || gimple_call_ctrl_altering_p (s1) != gimple_call_ctrl_altering_p (s2)
|
|
753 || gimple_call_tail_p (s1) != gimple_call_tail_p (s2)
|
|
754 || gimple_call_return_slot_opt_p (s1) != gimple_call_return_slot_opt_p (s2)
|
|
755 || gimple_call_from_thunk_p (s1) != gimple_call_from_thunk_p (s2)
|
|
756 || gimple_call_va_arg_pack_p (s1) != gimple_call_va_arg_pack_p (s2)
|
131
|
757 || gimple_call_alloca_for_var_p (s1) != gimple_call_alloca_for_var_p (s2))
|
111
|
758 return false;
|
|
759
|
|
760 if (gimple_call_internal_p (s1)
|
|
761 && gimple_call_internal_fn (s1) != gimple_call_internal_fn (s2))
|
|
762 return false;
|
|
763
|
|
764 tree fntype1 = gimple_call_fntype (s1);
|
|
765 tree fntype2 = gimple_call_fntype (s2);
|
|
766 if ((fntype1 && !fntype2)
|
|
767 || (!fntype1 && fntype2)
|
|
768 || (fntype1 && !types_compatible_p (fntype1, fntype2)))
|
|
769 return return_false_with_msg ("call function types are not compatible");
|
|
770
|
|
771 tree chain1 = gimple_call_chain (s1);
|
|
772 tree chain2 = gimple_call_chain (s2);
|
|
773 if ((chain1 && !chain2)
|
|
774 || (!chain1 && chain2)
|
|
775 || !compare_operand (chain1, chain2))
|
|
776 return return_false_with_msg ("static call chains are different");
|
|
777
|
|
778 /* Checking of argument. */
|
|
779 for (i = 0; i < gimple_call_num_args (s1); ++i)
|
|
780 {
|
|
781 t1 = gimple_call_arg (s1, i);
|
|
782 t2 = gimple_call_arg (s2, i);
|
|
783
|
|
784 if (!compare_memory_operand (t1, t2))
|
|
785 return return_false_with_msg ("memory operands are different");
|
|
786 }
|
|
787
|
|
788 /* Return value checking. */
|
|
789 t1 = gimple_get_lhs (s1);
|
|
790 t2 = gimple_get_lhs (s2);
|
|
791
|
|
792 return compare_memory_operand (t1, t2);
|
|
793 }
|
|
794
|
|
795
|
|
796 /* Verifies for given GIMPLEs S1 and S2 that
|
|
797 assignment statements are semantically equivalent. */
|
|
798
|
|
799 bool
|
|
800 func_checker::compare_gimple_assign (gimple *s1, gimple *s2)
|
|
801 {
|
|
802 tree arg1, arg2;
|
|
803 tree_code code1, code2;
|
|
804 unsigned i;
|
|
805
|
|
806 code1 = gimple_expr_code (s1);
|
|
807 code2 = gimple_expr_code (s2);
|
|
808
|
|
809 if (code1 != code2)
|
|
810 return false;
|
|
811
|
|
812 code1 = gimple_assign_rhs_code (s1);
|
|
813 code2 = gimple_assign_rhs_code (s2);
|
|
814
|
|
815 if (code1 != code2)
|
|
816 return false;
|
|
817
|
|
818 for (i = 0; i < gimple_num_ops (s1); i++)
|
|
819 {
|
|
820 arg1 = gimple_op (s1, i);
|
|
821 arg2 = gimple_op (s2, i);
|
|
822
|
|
823 if (!compare_memory_operand (arg1, arg2))
|
|
824 return return_false_with_msg ("memory operands are different");
|
|
825 }
|
|
826
|
|
827
|
|
828 return true;
|
|
829 }
|
|
830
|
|
831 /* Verifies for given GIMPLEs S1 and S2 that
|
|
832 condition statements are semantically equivalent. */
|
|
833
|
|
834 bool
|
|
835 func_checker::compare_gimple_cond (gimple *s1, gimple *s2)
|
|
836 {
|
|
837 tree t1, t2;
|
|
838 tree_code code1, code2;
|
|
839
|
|
840 code1 = gimple_expr_code (s1);
|
|
841 code2 = gimple_expr_code (s2);
|
|
842
|
|
843 if (code1 != code2)
|
|
844 return false;
|
|
845
|
|
846 t1 = gimple_cond_lhs (s1);
|
|
847 t2 = gimple_cond_lhs (s2);
|
|
848
|
|
849 if (!compare_operand (t1, t2))
|
|
850 return false;
|
|
851
|
|
852 t1 = gimple_cond_rhs (s1);
|
|
853 t2 = gimple_cond_rhs (s2);
|
|
854
|
|
855 return compare_operand (t1, t2);
|
|
856 }
|
|
857
|
|
858 /* Verifies that tree labels T1 and T2 correspond in FUNC1 and FUNC2. */
|
|
859
|
|
860 bool
|
|
861 func_checker::compare_tree_ssa_label (tree t1, tree t2)
|
|
862 {
|
|
863 return compare_operand (t1, t2);
|
|
864 }
|
|
865
|
|
866 /* Verifies for given GIMPLE_LABEL stmts S1 and S2 that
|
|
867 label statements are semantically equivalent. */
|
|
868
|
|
869 bool
|
|
870 func_checker::compare_gimple_label (const glabel *g1, const glabel *g2)
|
|
871 {
|
|
872 if (m_ignore_labels)
|
|
873 return true;
|
|
874
|
|
875 tree t1 = gimple_label_label (g1);
|
|
876 tree t2 = gimple_label_label (g2);
|
|
877
|
|
878 if (FORCED_LABEL (t1) || FORCED_LABEL (t2))
|
|
879 return return_false_with_msg ("FORCED_LABEL");
|
|
880
|
|
881 /* As the pass build BB to label mapping, no further check is needed. */
|
|
882 return true;
|
|
883 }
|
|
884
|
|
885 /* Verifies for given GIMPLE_SWITCH stmts S1 and S2 that
|
|
886 switch statements are semantically equivalent. */
|
|
887
|
|
888 bool
|
|
889 func_checker::compare_gimple_switch (const gswitch *g1, const gswitch *g2)
|
|
890 {
|
|
891 unsigned lsize1, lsize2, i;
|
|
892
|
|
893 lsize1 = gimple_switch_num_labels (g1);
|
|
894 lsize2 = gimple_switch_num_labels (g2);
|
|
895
|
|
896 if (lsize1 != lsize2)
|
|
897 return false;
|
|
898
|
|
899 tree t1 = gimple_switch_index (g1);
|
|
900 tree t2 = gimple_switch_index (g2);
|
|
901
|
|
902 if (!compare_operand (t1, t2))
|
|
903 return false;
|
|
904
|
|
905 for (i = 0; i < lsize1; i++)
|
|
906 {
|
|
907 tree label1 = gimple_switch_label (g1, i);
|
|
908 tree label2 = gimple_switch_label (g2, i);
|
|
909
|
|
910 /* Label LOW and HIGH comparison. */
|
|
911 tree low1 = CASE_LOW (label1);
|
|
912 tree low2 = CASE_LOW (label2);
|
|
913
|
|
914 if (!tree_int_cst_equal (low1, low2))
|
|
915 return return_false_with_msg ("case low values are different");
|
|
916
|
|
917 tree high1 = CASE_HIGH (label1);
|
|
918 tree high2 = CASE_HIGH (label2);
|
|
919
|
|
920 if (!tree_int_cst_equal (high1, high2))
|
|
921 return return_false_with_msg ("case high values are different");
|
|
922
|
|
923 if (TREE_CODE (label1) == CASE_LABEL_EXPR
|
|
924 && TREE_CODE (label2) == CASE_LABEL_EXPR)
|
|
925 {
|
|
926 label1 = CASE_LABEL (label1);
|
|
927 label2 = CASE_LABEL (label2);
|
|
928
|
|
929 if (!compare_operand (label1, label2))
|
|
930 return return_false_with_msg ("switch label_exprs are different");
|
|
931 }
|
|
932 else if (!tree_int_cst_equal (label1, label2))
|
|
933 return return_false_with_msg ("switch labels are different");
|
|
934 }
|
|
935
|
|
936 return true;
|
|
937 }
|
|
938
|
|
939 /* Verifies for given GIMPLE_RETURN stmts S1 and S2 that
|
|
940 return statements are semantically equivalent. */
|
|
941
|
|
942 bool
|
|
943 func_checker::compare_gimple_return (const greturn *g1, const greturn *g2)
|
|
944 {
|
|
945 tree t1, t2;
|
|
946
|
|
947 t1 = gimple_return_retval (g1);
|
|
948 t2 = gimple_return_retval (g2);
|
|
949
|
|
950 /* Void return type. */
|
|
951 if (t1 == NULL && t2 == NULL)
|
|
952 return true;
|
|
953 else
|
|
954 return compare_operand (t1, t2);
|
|
955 }
|
|
956
|
|
957 /* Verifies for given GIMPLEs S1 and S2 that
|
|
958 goto statements are semantically equivalent. */
|
|
959
|
|
960 bool
|
|
961 func_checker::compare_gimple_goto (gimple *g1, gimple *g2)
|
|
962 {
|
|
963 tree dest1, dest2;
|
|
964
|
|
965 dest1 = gimple_goto_dest (g1);
|
|
966 dest2 = gimple_goto_dest (g2);
|
|
967
|
|
968 if (TREE_CODE (dest1) != TREE_CODE (dest2) || TREE_CODE (dest1) != SSA_NAME)
|
|
969 return false;
|
|
970
|
|
971 return compare_operand (dest1, dest2);
|
|
972 }
|
|
973
|
|
974 /* Verifies for given GIMPLE_RESX stmts S1 and S2 that
|
|
975 resx statements are semantically equivalent. */
|
|
976
|
|
977 bool
|
|
978 func_checker::compare_gimple_resx (const gresx *g1, const gresx *g2)
|
|
979 {
|
|
980 return gimple_resx_region (g1) == gimple_resx_region (g2);
|
|
981 }
|
|
982
|
|
983 /* Verifies for given GIMPLEs S1 and S2 that ASM statements are equivalent.
|
|
984 For the beginning, the pass only supports equality for
|
|
985 '__asm__ __volatile__ ("", "", "", "memory")'. */
|
|
986
|
|
987 bool
|
|
988 func_checker::compare_gimple_asm (const gasm *g1, const gasm *g2)
|
|
989 {
|
|
990 if (gimple_asm_volatile_p (g1) != gimple_asm_volatile_p (g2))
|
|
991 return false;
|
|
992
|
|
993 if (gimple_asm_input_p (g1) != gimple_asm_input_p (g2))
|
|
994 return false;
|
|
995
|
|
996 if (gimple_asm_ninputs (g1) != gimple_asm_ninputs (g2))
|
|
997 return false;
|
|
998
|
|
999 if (gimple_asm_noutputs (g1) != gimple_asm_noutputs (g2))
|
|
1000 return false;
|
|
1001
|
|
1002 /* We do not suppport goto ASM statement comparison. */
|
|
1003 if (gimple_asm_nlabels (g1) || gimple_asm_nlabels (g2))
|
|
1004 return false;
|
|
1005
|
|
1006 if (gimple_asm_nclobbers (g1) != gimple_asm_nclobbers (g2))
|
|
1007 return false;
|
|
1008
|
|
1009 if (strcmp (gimple_asm_string (g1), gimple_asm_string (g2)) != 0)
|
|
1010 return return_false_with_msg ("ASM strings are different");
|
|
1011
|
|
1012 for (unsigned i = 0; i < gimple_asm_ninputs (g1); i++)
|
|
1013 {
|
|
1014 tree input1 = gimple_asm_input_op (g1, i);
|
|
1015 tree input2 = gimple_asm_input_op (g2, i);
|
|
1016
|
|
1017 if (!compare_asm_inputs_outputs (input1, input2))
|
|
1018 return return_false_with_msg ("ASM input is different");
|
|
1019 }
|
|
1020
|
|
1021 for (unsigned i = 0; i < gimple_asm_noutputs (g1); i++)
|
|
1022 {
|
|
1023 tree output1 = gimple_asm_output_op (g1, i);
|
|
1024 tree output2 = gimple_asm_output_op (g2, i);
|
|
1025
|
|
1026 if (!compare_asm_inputs_outputs (output1, output2))
|
|
1027 return return_false_with_msg ("ASM output is different");
|
|
1028 }
|
|
1029
|
|
1030 for (unsigned i = 0; i < gimple_asm_nclobbers (g1); i++)
|
|
1031 {
|
|
1032 tree clobber1 = gimple_asm_clobber_op (g1, i);
|
|
1033 tree clobber2 = gimple_asm_clobber_op (g2, i);
|
|
1034
|
|
1035 if (!operand_equal_p (TREE_VALUE (clobber1), TREE_VALUE (clobber2),
|
|
1036 OEP_ONLY_CONST))
|
|
1037 return return_false_with_msg ("ASM clobber is different");
|
|
1038 }
|
|
1039
|
|
1040 return true;
|
|
1041 }
|
|
1042
|
|
1043 } // ipa_icf_gimple namespace
|