/* Interprocedural Identical Code Folding pass
- Copyright (C) 2014 Free Software Foundation, Inc.
+ Copyright (C) 2014-2015 Free Software Foundation, Inc.
Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
#include "config.h"
#include "system.h"
#include "coretypes.h"
+#include "alias.h"
+#include "symtab.h"
+#include "options.h"
#include "tree.h"
+#include "fold-const.h"
#include "predict.h"
-#include "vec.h"
-#include "hashtab.h"
-#include "hash-set.h"
-#include "machmode.h"
#include "tm.h"
#include "hard-reg-set.h"
-#include "input.h"
#include "function.h"
#include "basic-block.h"
#include "tree-ssa-alias.h"
#include "internal-fn.h"
#include "gimple-expr.h"
-#include "is-a.h"
#include "gimple.h"
+#include "rtl.h"
+#include "flags.h"
+#include "insn-config.h"
+#include "expmed.h"
+#include "dojump.h"
+#include "explow.h"
+#include "calls.h"
+#include "emit-rtl.h"
+#include "varasm.h"
+#include "stmt.h"
#include "expr.h"
#include "gimple-iterator.h"
#include "gimple-ssa.h"
#include "gimple-pretty-print.h"
#include "cfgloop.h"
#include "except.h"
-#include "hash-map.h"
-#include "plugin-api.h"
-#include "ipa-ref.h"
#include "cgraph.h"
#include "data-streamer.h"
#include "ipa-utils.h"
#include <list>
#include "tree-ssanames.h"
#include "tree-eh.h"
+#include "builtins.h"
#include "ipa-icf-gimple.h"
#include "ipa-icf.h"
bool
func_checker::compare_ssa_name (tree t1, tree t2)
{
+ gcc_assert (TREE_CODE (t1) == SSA_NAME);
+ gcc_assert (TREE_CODE (t2) == SSA_NAME);
+
unsigned i1 = SSA_NAME_VERSION (t1);
unsigned i2 = SSA_NAME_VERSION (t2);
else if (m_target_ssa_names[i2] != (int) i1)
return false;
+ if (SSA_NAME_IS_DEFAULT_DEF (t1))
+ {
+ tree b1 = SSA_NAME_VAR (t1);
+ tree b2 = SSA_NAME_VAR (t2);
+
+ if (b1 == NULL && b2 == NULL)
+ return true;
+
+ if (b1 == NULL || b2 == NULL || TREE_CODE (b1) != TREE_CODE (b2))
+ return return_false ();
+
+ return compare_cst_or_decl (b1, b2);
+ }
+
return true;
}
&& DECL_BY_REFERENCE (t1) != DECL_BY_REFERENCE (t2))
return return_false_with_msg ("DECL_BY_REFERENCE flags are different");
- if (!compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2),
- m_compare_polymorphic))
+ if (!compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
+ return return_false ();
+
+ /* TODO: we are actually too strict here. We only need to compare if
+ T1 can be used in polymorphic call. */
+ if (TREE_ADDRESSABLE (t1)
+ && m_compare_polymorphic
+ && !compatible_polymorphic_types_p (TREE_TYPE (t1), TREE_TYPE (t2),
+ false))
+ return return_false ();
+
+ if ((t == VAR_DECL || t == PARM_DECL || t == RESULT_DECL)
+ && DECL_BY_REFERENCE (t1)
+ && m_compare_polymorphic
+ && !compatible_polymorphic_types_p (TREE_TYPE (t1), TREE_TYPE (t2),
+ true))
return return_false ();
bool existed_p;
return true;
}
+/* Return true if T1 and T2 are same for purposes of ipa-polymorphic-call
+ analysis. COMPARE_PTR indicates if types of pointers needs to be
+ considered. */
+
+bool
+func_checker::compatible_polymorphic_types_p (tree t1, tree t2,
+ bool compare_ptr)
+{
+ gcc_assert (TREE_CODE (t1) != FUNCTION_TYPE && TREE_CODE (t1) != METHOD_TYPE);
+
+ /* Pointer types generally give no information. */
+ if (POINTER_TYPE_P (t1))
+ {
+ if (!compare_ptr)
+ return true;
+ return func_checker::compatible_polymorphic_types_p (TREE_TYPE (t1),
+ TREE_TYPE (t2),
+ false);
+ }
+
+ /* If types contain a polymorphic types, match them. */
+ bool c1 = contains_polymorphic_type_p (t1);
+ bool c2 = contains_polymorphic_type_p (t2);
+ if (!c1 && !c2)
+ return true;
+ if (!c1 || !c2)
+ return return_false_with_msg ("one type is not polymorphic");
+ if (!types_must_be_same_for_odr (t1, t2))
+ return return_false_with_msg ("types are not same for ODR");
+ return true;
+}
+
/* Return true if types are compatible from perspective of ICF. */
-bool func_checker::compatible_types_p (tree t1, tree t2,
- bool compare_polymorphic,
- bool first_argument)
+bool
+func_checker::compatible_types_p (tree t1, tree t2)
{
if (TREE_CODE (t1) != TREE_CODE (t2))
return return_false_with_msg ("different tree types");
+ if (TYPE_RESTRICT (t1) != TYPE_RESTRICT (t2))
+ return return_false_with_msg ("restrict flags are different");
+
if (!types_compatible_p (t1, t2))
return return_false_with_msg ("types are not compatible");
if (get_alias_set (t1) != get_alias_set (t2))
return return_false_with_msg ("alias sets are different");
- /* We call contains_polymorphic_type_p with this pointer type. */
- if (first_argument && TREE_CODE (t1) == POINTER_TYPE)
+ return true;
+}
+
+/* Function compare for equality given memory operands T1 and T2. */
+
+bool
+func_checker::compare_memory_operand (tree t1, tree t2)
+{
+ if (!t1 && !t2)
+ return true;
+ else if (!t1 || !t2)
+ return false;
+
+ ao_ref r1, r2;
+ ao_ref_init (&r1, t1);
+ ao_ref_init (&r2, t2);
+
+ tree b1 = ao_ref_base (&r1);
+ tree b2 = ao_ref_base (&r2);
+
+ bool source_is_memop = DECL_P (b1) || INDIRECT_REF_P (b1)
+ || TREE_CODE (b1) == MEM_REF
+ || TREE_CODE (b1) == TARGET_MEM_REF;
+
+ bool target_is_memop = DECL_P (b2) || INDIRECT_REF_P (b2)
+ || TREE_CODE (b2) == MEM_REF
+ || TREE_CODE (b2) == TARGET_MEM_REF;
+
+ /* Compare alias sets for memory operands. */
+ if (source_is_memop && target_is_memop)
{
- t1 = TREE_TYPE (t1);
- t2 = TREE_TYPE (t2);
+ if (TREE_THIS_VOLATILE (t1) != TREE_THIS_VOLATILE (t2))
+ return return_false_with_msg ("different operand volatility");
+
+ if (ao_ref_alias_set (&r1) != ao_ref_alias_set (&r2)
+ || ao_ref_base_alias_set (&r1) != ao_ref_base_alias_set (&r2))
+ return return_false_with_msg ("ao alias sets are different");
+
+ /* We can't simply use get_object_alignment_1 on the full
+ reference as for accesses with variable indexes this reports
+ too conservative alignment. We also can't use the ao_ref_base
+ base objects as ao_ref_base happily strips MEM_REFs around
+ decls even though that may carry alignment info. */
+ b1 = t1;
+ while (handled_component_p (b1))
+ b1 = TREE_OPERAND (b1, 0);
+ b2 = t2;
+ while (handled_component_p (b2))
+ b2 = TREE_OPERAND (b2, 0);
+ unsigned int align1, align2;
+ unsigned HOST_WIDE_INT tem;
+ get_object_alignment_1 (b1, &align1, &tem);
+ get_object_alignment_1 (b2, &align2, &tem);
+ if (align1 != align2)
+ return return_false_with_msg ("different access alignment");
+
+ /* Similarly we have to compare dependence info where equality
+ tells us we are safe (even some unequal values would be safe
+ but then we have to maintain a map of bases and cliques). */
+ unsigned short clique1 = 0, base1 = 0, clique2 = 0, base2 = 0;
+ if (TREE_CODE (b1) == MEM_REF)
+ {
+ clique1 = MR_DEPENDENCE_CLIQUE (b1);
+ base1 = MR_DEPENDENCE_BASE (b1);
+ }
+ if (TREE_CODE (b2) == MEM_REF)
+ {
+ clique2 = MR_DEPENDENCE_CLIQUE (b2);
+ base2 = MR_DEPENDENCE_BASE (b2);
+ }
+ if (clique1 != clique2 || base1 != base2)
+ return return_false_with_msg ("different dependence info");
}
- if (compare_polymorphic)
- if (contains_polymorphic_type_p (t1) || contains_polymorphic_type_p (t2))
+ return compare_operand (t1, t2);
+}
+
+/* Function compare for equality given trees T1 and T2 which
+ can be either a constant or a declaration type. */
+
+bool
+func_checker::compare_cst_or_decl (tree t1, tree t2)
+{
+ bool ret;
+
+ switch (TREE_CODE (t1))
+ {
+ case INTEGER_CST:
+ case COMPLEX_CST:
+ case VECTOR_CST:
+ case STRING_CST:
+ case REAL_CST:
+ {
+ ret = compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2))
+ && operand_equal_p (t1, t2, OEP_ONLY_CONST);
+ return return_with_debug (ret);
+ }
+ case FUNCTION_DECL:
+ /* All function decls are in the symbol table and known to match
+ before we start comparing bodies. */
+ return true;
+ case VAR_DECL:
+ return return_with_debug (compare_variable_decl (t1, t2));
+ case FIELD_DECL:
{
- if (!contains_polymorphic_type_p (t1) || !contains_polymorphic_type_p (t2))
- return return_false_with_msg ("one type is not polymorphic");
+ tree offset1 = DECL_FIELD_OFFSET (t1);
+ tree offset2 = DECL_FIELD_OFFSET (t2);
- if (!types_must_be_same_for_odr (t1, t2))
- return return_false_with_msg ("types are not same for ODR");
+ tree bit_offset1 = DECL_FIELD_BIT_OFFSET (t1);
+ tree bit_offset2 = DECL_FIELD_BIT_OFFSET (t2);
+
+ ret = compare_operand (offset1, offset2)
+ && compare_operand (bit_offset1, bit_offset2);
+
+ return return_with_debug (ret);
}
+ case LABEL_DECL:
+ {
+ int *bb1 = m_label_bb_map.get (t1);
+ int *bb2 = m_label_bb_map.get (t2);
- return true;
+ return return_with_debug (*bb1 == *bb2);
+ }
+ case PARM_DECL:
+ case RESULT_DECL:
+ case CONST_DECL:
+ {
+ ret = compare_decl (t1, t2);
+ return return_with_debug (ret);
+ }
+ default:
+ gcc_unreachable ();
+ }
}
-/* Function responsible for comparison of handled components T1 and T2.
+/* Function responsible for comparison of various operands T1 and T2.
If these components, from functions FUNC1 and FUNC2, are equal, true
is returned. */
bool
func_checker::compare_operand (tree t1, tree t2)
{
- tree base1, base2, x1, x2, y1, y2, z1, z2;
- HOST_WIDE_INT offset1 = 0, offset2 = 0;
+ tree x1, x2, y1, y2, z1, z2;
bool ret;
if (!t1 && !t2)
tree tt1 = TREE_TYPE (t1);
tree tt2 = TREE_TYPE (t2);
- if (TREE_THIS_VOLATILE (t1) != TREE_THIS_VOLATILE (t2))
- return return_false_with_msg ("different operand volatility");
-
if (!func_checker::compatible_types_p (tt1, tt2))
return false;
- base1 = get_addr_base_and_unit_offset (t1, &offset1);
- base2 = get_addr_base_and_unit_offset (t2, &offset2);
-
- if (base1 && base2)
- {
- if (offset1 != offset2)
- return return_false_with_msg ("base offsets are different");
-
- t1 = base1;
- t2 = base2;
- }
-
if (TREE_CODE (t1) != TREE_CODE (t2))
return return_false ();
}
case ARRAY_REF:
case ARRAY_RANGE_REF:
+ /* First argument is the array, second is the index. */
x1 = TREE_OPERAND (t1, 0);
x2 = TREE_OPERAND (t2, 0);
y1 = TREE_OPERAND (t1, 1);
if (!compare_operand (array_ref_element_size (t1),
array_ref_element_size (t2)))
return return_false_with_msg ("");
+
if (!compare_operand (x1, x2))
return return_false_with_msg ("");
return compare_operand (y1, y2);
if (!compare_operand (x1, x2))
return return_false_with_msg ("");
- if (get_alias_set (TREE_TYPE (y1)) != get_alias_set (TREE_TYPE (y2)))
- return return_false_with_msg ("alias set for MEM_REF offsets are different");
-
- ao_ref r1, r2;
- ao_ref_init (&r1, t1);
- ao_ref_init (&r2, t2);
- if (ao_ref_alias_set (&r1) != ao_ref_alias_set (&r2)
- || ao_ref_base_alias_set (&r1) != ao_ref_base_alias_set (&r2))
- return return_false_with_msg ("ao alias sets are different");
-
/* Type of the offset on MEM_REF does not matter. */
return wi::to_offset (y1) == wi::to_offset (y2);
}
y2 = TREE_OPERAND (t2, 1);
ret = compare_operand (x1, x2)
- && compare_operand (y1, y2);
+ && compare_cst_or_decl (y1, y2);
return return_with_debug (ret);
}
/* Virtual table call. */
case OBJ_TYPE_REF:
{
- x1 = TREE_OPERAND (t1, 0);
- x2 = TREE_OPERAND (t2, 0);
- y1 = TREE_OPERAND (t1, 1);
- y2 = TREE_OPERAND (t2, 1);
- z1 = TREE_OPERAND (t1, 2);
- z2 = TREE_OPERAND (t2, 2);
-
- ret = compare_operand (x1, x2)
- && compare_operand (y1, y2)
- && compare_operand (z1, z2);
+ if (!compare_ssa_name (OBJ_TYPE_REF_EXPR (t1), OBJ_TYPE_REF_EXPR (t2)))
+ return return_false ();
+ if (opt_for_fn (m_source_func_decl, flag_devirtualize)
+ && virtual_method_call_p (t1))
+ {
+ if (tree_to_uhwi (OBJ_TYPE_REF_TOKEN (t1))
+ != tree_to_uhwi (OBJ_TYPE_REF_TOKEN (t2)))
+ return return_false_with_msg ("OBJ_TYPE_REF token mismatch");
+ if (!types_same_for_odr (obj_type_ref_class (t1),
+ obj_type_ref_class (t2)))
+ return return_false_with_msg ("OBJ_TYPE_REF OTR type mismatch");
+ if (!compare_operand (OBJ_TYPE_REF_OBJECT (t1),
+ OBJ_TYPE_REF_OBJECT (t2)))
+ return return_false_with_msg ("OBJ_TYPE_REF object mismatch");
+ }
- return return_with_debug (ret);
+ return return_with_debug (true);
}
+ case IMAGPART_EXPR:
+ case REALPART_EXPR:
case ADDR_EXPR:
{
x1 = TREE_OPERAND (t1, 0);
ret = compare_operand (x1, x2);
return return_with_debug (ret);
}
- case SSA_NAME:
+ case BIT_FIELD_REF:
{
- ret = compare_ssa_name (t1, t2);
-
- if (!ret)
- return return_with_debug (ret);
+ x1 = TREE_OPERAND (t1, 0);
+ x2 = TREE_OPERAND (t2, 0);
+ y1 = TREE_OPERAND (t1, 1);
+ y2 = TREE_OPERAND (t2, 1);
+ z1 = TREE_OPERAND (t1, 2);
+ z2 = TREE_OPERAND (t2, 2);
- if (SSA_NAME_IS_DEFAULT_DEF (t1))
- {
- tree b1 = SSA_NAME_VAR (t1);
- tree b2 = SSA_NAME_VAR (t2);
-
- if (b1 == NULL && b2 == NULL)
- return true;
-
- if (b1 == NULL || b2 == NULL || TREE_CODE (b1) != TREE_CODE (b2))
- return return_false ();
-
- switch (TREE_CODE (b1))
- {
- case VAR_DECL:
- return return_with_debug (compare_variable_decl (t1, t2));
- case PARM_DECL:
- case RESULT_DECL:
- ret = compare_decl (b1, b2);
- return return_with_debug (ret);
- default:
- return return_false_with_msg ("Unknown TREE code reached");
- }
- }
- else
- return true;
- }
- case INTEGER_CST:
- {
- ret = compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2))
- && wi::to_offset (t1) == wi::to_offset (t2);
+ ret = compare_operand (x1, x2)
+ && compare_cst_or_decl (y1, y2)
+ && compare_cst_or_decl (z1, z2);
return return_with_debug (ret);
}
+ case SSA_NAME:
+ return compare_ssa_name (t1, t2);
+ case INTEGER_CST:
case COMPLEX_CST:
case VECTOR_CST:
case STRING_CST:
case REAL_CST:
- {
- ret = operand_equal_p (t1, t2, OEP_ONLY_CONST);
- return return_with_debug (ret);
- }
case FUNCTION_DECL:
- {
- ret = compare_function_decl (t1, t2);
- return return_with_debug (ret);
- }
case VAR_DECL:
- return return_with_debug (compare_variable_decl (t1, t2));
case FIELD_DECL:
- {
- tree offset1 = DECL_FIELD_OFFSET (t1);
- tree offset2 = DECL_FIELD_OFFSET (t2);
-
- tree bit_offset1 = DECL_FIELD_BIT_OFFSET (t1);
- tree bit_offset2 = DECL_FIELD_BIT_OFFSET (t2);
-
- ret = compare_operand (offset1, offset2)
- && compare_operand (bit_offset1, bit_offset2);
-
- return return_with_debug (ret);
- }
case LABEL_DECL:
- {
- int *bb1 = m_label_bb_map.get (t1);
- int *bb2 = m_label_bb_map.get (t2);
-
- return return_with_debug (*bb1 == *bb2);
- }
case PARM_DECL:
case RESULT_DECL:
case CONST_DECL:
- case BIT_FIELD_REF:
- {
- ret = compare_decl (t1, t2);
- return return_with_debug (ret);
- }
+ return compare_cst_or_decl (t1, t2);
default:
return return_false_with_msg ("Unknown TREE code reached");
}
return true;
}
-/* Verifies that trees T1 and T2, representing function declarations
- are equivalent from perspective of ICF. */
-
-bool
-func_checker::compare_function_decl (tree t1, tree t2)
-{
- bool ret = false;
-
- if (t1 == t2)
- return true;
-
- symtab_node *n1 = symtab_node::get (t1);
- symtab_node *n2 = symtab_node::get (t2);
-
- if (m_ignored_source_nodes != NULL && m_ignored_target_nodes != NULL)
- {
- ret = m_ignored_source_nodes->contains (n1)
- && m_ignored_target_nodes->contains (n2);
-
- if (ret)
- return true;
- }
-
- /* If function decl is WEAKREF, we compare targets. */
- cgraph_node *f1 = cgraph_node::get (t1);
- cgraph_node *f2 = cgraph_node::get (t2);
-
- if(f1 && f2 && f1->weakref && f2->weakref)
- ret = f1->alias_target == f2->alias_target;
-
- return ret;
-}
-
/* Verifies that trees T1 and T2 do correspond. */
bool
if (t1 == t2)
return true;
- if (TREE_CODE (t1) == VAR_DECL && (DECL_EXTERNAL (t1) || TREE_STATIC (t1)))
- {
- symtab_node *n1 = symtab_node::get (t1);
- symtab_node *n2 = symtab_node::get (t2);
+ if (DECL_ALIGN (t1) != DECL_ALIGN (t2))
+ return return_false_with_msg ("alignments are different");
- if (m_ignored_source_nodes != NULL && m_ignored_target_nodes != NULL)
- {
- ret = m_ignored_source_nodes->contains (n1)
- && m_ignored_target_nodes->contains (n2);
+ if (DECL_HARD_REGISTER (t1) != DECL_HARD_REGISTER (t2))
+ return return_false_with_msg ("DECL_HARD_REGISTER are different");
- if (ret)
- return true;
- }
- }
+ if (DECL_HARD_REGISTER (t1)
+ && DECL_ASSEMBLER_NAME (t1) != DECL_ASSEMBLER_NAME (t2))
+ return return_false_with_msg ("HARD REGISTERS are different");
+
+ /* Symbol table variables are known to match before we start comparing
+ bodies. */
+ if (decl_in_symtab_p (t1))
+ return decl_in_symtab_p (t2);
ret = compare_decl (t1, t2);
return return_with_debug (ret);
return return_different_stmts (s1, s2, "GIMPLE_SWITCH");
break;
case GIMPLE_DEBUG:
+ break;
case GIMPLE_EH_DISPATCH:
+ if (gimple_eh_dispatch_region (as_a <geh_dispatch *> (s1))
+ != gimple_eh_dispatch_region (as_a <geh_dispatch *> (s2)))
+ return return_different_stmts (s1, s2, "GIMPLE_EH_DISPATCH");
break;
case GIMPLE_RESX:
if (!compare_gimple_resx (as_a <gresx *> (s1),
break;
case GIMPLE_PREDICT:
case GIMPLE_NOP:
- return true;
+ break;
default:
return return_false_with_msg ("Unknown GIMPLE code reached");
}
t1 = gimple_call_arg (s1, i);
t2 = gimple_call_arg (s2, i);
- if (!compare_operand (t1, t2))
- return false;
+ if (!compare_memory_operand (t1, t2))
+ return return_false_with_msg ("memory operands are different");
}
/* Return value checking. */
t1 = gimple_get_lhs (s1);
t2 = gimple_get_lhs (s2);
- return compare_operand (t1, t2);
+ return compare_memory_operand (t1, t2);
}
arg1 = gimple_op (s1, i);
arg2 = gimple_op (s2, i);
- if (!compare_operand (arg1, arg2))
- return false;
+ if (!compare_memory_operand (arg1, arg2))
+ return return_false_with_msg ("memory operands are different");
}