From b0702ac5588333e27d7ec43d21d704521f7a05c6 Mon Sep 17 00:00:00 2001 From: David Malcolm Date: Tue, 27 Oct 2020 09:51:19 -0400 Subject: [PATCH] analyzer: eliminate non-determinism in logs This patch and the followup eliminate various forms of non-determinism in the analyzer due to changing pointer values. This patch fixes churn seen when diffing analyzer logs. The patch avoids embedding pointers in various places, and adds sorting when dumping hash_set and hash_map for various analyzer types. Doing so requires implementing a way to sort svalue instances, and assigning UIDs to gimple statements. Tested both patches together via a script that runs a testcase 100 times, and then using diff and md5sum to verify that the results are consistent in the face of address space randomization: FILENAME=$1 rm $FILENAME.* for i in `seq 1 100`; do echo "iteration: $i" ./xgcc -B. -fanalyzer -c ../../src/gcc/testsuite/gcc.dg/analyzer/$FILENAME \ --Wanalyzer-too-complex \ -fdump-analyzer-supergraph \ -fdump-analyzer-exploded-graph \ -fdump-analyzer \ -fdump-noaddr \ -fdump-analyzer-exploded-nodes-2 mv $FILENAME.supergraph.dot $FILENAME.$i.supergraph.dot mv $FILENAME.analyzer.txt $FILENAME.$i.analyzer.txt mv $FILENAME.supergraph-eg.dot $FILENAME.$i.supergraph-eg.dot mv $FILENAME.eg.txt $FILENAME.$i.eg.txt mv $FILENAME.eg.dot $FILENAME.$i.eg.dot done gcc/analyzer/ChangeLog: * engine.cc (setjmp_record::cmp): New. (supernode_cluster::dump_dot): Avoid embedding pointer in cluster name. (supernode_cluster::cmp_ptr_ptr): New. (function_call_string_cluster::dump_dot): Avoid embedding pointer in cluster name. Sort m_map when dumping child clusters. (function_call_string_cluster::cmp_ptr_ptr): New. (root_cluster::dump_dot): Sort m_map when dumping child clusters. * program-point.cc (function_point::cmp): New. (function_point::cmp_ptr): New. * program-point.h (function_point::cmp): New decl. (function_point::cmp_ptr): New decl. * program-state.cc (sm_state_map::print): Sort the values. Guard the printing of pointers with !flag_dump_noaddr. (program_state::prune_for_point): Sort the regions. (log_set_of_svalues): Sort the values. Guard the printing of pointers with !flag_dump_noaddr. * region-model-manager.cc (log_uniq_map): Sort the values. * region-model-reachability.cc (dump_set): New function template. (reachable_regions::dump_to_pp): Use it. * region-model.h (svalue::cmp_ptr): New decl. (svalue::cmp_ptr_ptr): New decl. (setjmp_record::cmp): New decl. (placeholder_svalue::get_name): New accessor. (widening_svalue::get_point): New accessor. (compound_svalue::get_map): New accessor. (conjured_svalue::get_stmt): New accessor. (conjured_svalue::get_id_region): New accessor. (region::cmp_ptrs): Rename to... (region::cmp_ptr_ptr): ...this. * region.cc (region::cmp_ptrs): Rename to... (region::cmp_ptr_ptr): ...this. * state-purge.cc (state_purge_per_ssa_name::state_purge_per_ssa_name): Sort m_points_needing_name when dumping. * store.cc (concrete_binding::cmp_ptr_ptr): New. (symbolic_binding::cmp_ptr_ptr): New. (binding_map::cmp): New. (get_sorted_parent_regions): Update for renaming of region::cmp_ptrs to region::cmp_ptr_ptr. (store::dump_to_pp): Likewise. (store::to_json): Likewise. (store::can_merge_p): Sort the base regions before considering them. * store.h (concrete_binding::cmp_ptr_ptr): New decl. (symbolic_binding::cmp_ptr_ptr): New decl. (binding_map::cmp): New decl. * supergraph.cc (supergraph::supergraph): Assign UIDs to the gimple stmts. * svalue.cc (cmp_cst): New. (svalue::cmp_ptr): New. (svalue::cmp_ptr_ptr): New. --- gcc/analyzer/engine.cc | 64 ++++++- gcc/analyzer/program-point.cc | 27 +++ gcc/analyzer/program-point.h | 3 + gcc/analyzer/program-state.cc | 33 +++- gcc/analyzer/region-model-manager.cc | 41 +++-- gcc/analyzer/region-model-reachability.cc | 58 +++--- gcc/analyzer/region-model.h | 15 +- gcc/analyzer/region.cc | 5 +- gcc/analyzer/state-purge.cc | 10 +- gcc/analyzer/store.cc | 82 ++++++++- gcc/analyzer/store.h | 6 + gcc/analyzer/supergraph.cc | 9 +- gcc/analyzer/svalue.cc | 205 ++++++++++++++++++++++ 13 files changed, 493 insertions(+), 65 deletions(-) diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc index be54f0256b7..49cd33e94da 100644 --- a/gcc/analyzer/engine.cc +++ b/gcc/analyzer/engine.cc @@ -149,6 +149,17 @@ impl_region_model_context::on_escaped_function (tree fndecl) m_eg->on_escaped_function (fndecl); } +/* struct setjmp_record. */ + +int +setjmp_record::cmp (const setjmp_record &rec1, const setjmp_record &rec2) +{ + if (int cmp_enode = rec1.m_enode->m_index - rec2.m_enode->m_index) + return cmp_enode; + gcc_assert (&rec1 == &rec2); + return 0; +} + /* class setjmp_svalue : public svalue. */ /* Implementation of svalue::accept vfunc for setjmp_svalue. */ @@ -3506,8 +3517,7 @@ public: void dump_dot (graphviz_out *gv, const dump_args_t &args) const FINAL OVERRIDE { - gv->println ("subgraph \"cluster_supernode_%p\" {", - (const void *)this); + gv->println ("subgraph \"cluster_supernode_%i\" {", m_supernode->m_index); gv->indent (); gv->println ("style=\"dashed\";"); gv->println ("label=\"SN: %i (bb: %i; scc: %i)\";", @@ -3529,6 +3539,17 @@ public: m_enodes.safe_push (en); } + /* Comparator for use by auto_vec::qsort. */ + + static int cmp_ptr_ptr (const void *p1, const void *p2) + { + const supernode_cluster *c1 + = *(const supernode_cluster * const *)p1; + const supernode_cluster *c2 + = *(const supernode_cluster * const *)p2; + return c1->m_supernode->m_index - c2->m_supernode->m_index; + } + private: const supernode *m_supernode; auto_vec m_enodes; @@ -3555,7 +3576,8 @@ public: { const char *funcname = function_name (m_fun); - gv->println ("subgraph \"cluster_function_%p\" {", (const void *)this); + gv->println ("subgraph \"cluster_function_%s\" {", + IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (m_fun->decl))); gv->indent (); gv->write_indent (); gv->print ("label=\"call string: "); @@ -3563,10 +3585,19 @@ public: gv->print (" function: %s \";", funcname); gv->print ("\n"); + /* Dump m_map, sorting it to avoid churn when comparing dumps. */ + auto_vec child_clusters (m_map.elements ()); for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter) - (*iter).second->dump_dot (gv, args); + child_clusters.quick_push ((*iter).second); + + child_clusters.qsort (supernode_cluster::cmp_ptr_ptr); + + unsigned i; + supernode_cluster *child_cluster; + FOR_EACH_VEC_ELT (child_clusters, i, child_cluster) + child_cluster->dump_dot (gv, args); /* Terminate subgraph. */ gv->outdent (); @@ -3588,6 +3619,21 @@ public: } } + /* Comparator for use by auto_vec. */ + + static int cmp_ptr_ptr (const void *p1, const void *p2) + { + const function_call_string_cluster *c1 + = *(const function_call_string_cluster * const *)p1; + const function_call_string_cluster *c2 + = *(const function_call_string_cluster * const *)p2; + if (int cmp_names + = strcmp (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c1->m_fun->decl)), + IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (c2->m_fun->decl)))) + return cmp_names; + return call_string::cmp (c1->m_cs, c2->m_cs); + } + private: function *m_fun; call_string m_cs; @@ -3680,10 +3726,18 @@ public: FOR_EACH_VEC_ELT (m_functionless_enodes, i, enode) enode->dump_dot (gv, args); + /* Dump m_map, sorting it to avoid churn when comparing dumps. */ + auto_vec child_clusters (m_map.elements ()); for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter) - (*iter).second->dump_dot (gv, args); + child_clusters.quick_push ((*iter).second); + + child_clusters.qsort (function_call_string_cluster::cmp_ptr_ptr); + + function_call_string_cluster *child_cluster; + FOR_EACH_VEC_ELT (child_clusters, i, child_cluster) + child_cluster->dump_dot (gv, args); } void add_node (exploded_node *en) FINAL OVERRIDE diff --git a/gcc/analyzer/program-point.cc b/gcc/analyzer/program-point.cc index 0aadd73a272..d8fde603374 100644 --- a/gcc/analyzer/program-point.cc +++ b/gcc/analyzer/program-point.cc @@ -558,6 +558,33 @@ function_point::cmp_within_supernode (const function_point &point_a, return result; } +/* Comparator for imposing an order on function_points. */ + +int +function_point::cmp (const function_point &point_a, + const function_point &point_b) +{ + int idx_a = point_a.m_supernode ? point_a.m_supernode->m_index : -1; + int idx_b = point_b.m_supernode ? point_b.m_supernode->m_index : -1; + if (int cmp_idx = idx_a - idx_b) + return cmp_idx; + gcc_assert (point_a.m_supernode == point_b.m_supernode); + if (point_a.m_supernode) + return cmp_within_supernode (point_a, point_b); + else + return 0; +} + +/* Comparator for use by vec::qsort. */ + +int +function_point::cmp_ptr (const void *p1, const void *p2) +{ + const function_point *fp1 = (const function_point *)p1; + const function_point *fp2 = (const function_point *)p2; + return cmp (*fp1, *fp2); +} + /* For PK_BEFORE_STMT, go to next stmt (or to PK_AFTER_SUPERNODE). */ void diff --git a/gcc/analyzer/program-point.h b/gcc/analyzer/program-point.h index d804621a715..2d1c3aba7cb 100644 --- a/gcc/analyzer/program-point.h +++ b/gcc/analyzer/program-point.h @@ -138,6 +138,9 @@ public: const function_point &point_b); static int cmp_within_supernode (const function_point &point_a, const function_point &point_b); + static int cmp (const function_point &point_a, + const function_point &point_b); + static int cmp_ptr (const void *p1, const void *p2); /* For before_stmt, go to next stmt. */ void next_stmt (); diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc index 5bb8907e340..2313a662e36 100644 --- a/gcc/analyzer/program-state.cc +++ b/gcc/analyzer/program-state.cc @@ -170,21 +170,29 @@ sm_state_map::print (const region_model *model, pp_newline (pp); first = false; } + auto_vec keys (m_map.elements ()); for (map_t::iterator iter = m_map.begin (); iter != m_map.end (); ++iter) + keys.quick_push ((*iter).first); + keys.qsort (svalue::cmp_ptr_ptr); + unsigned i; + const svalue *sval; + FOR_EACH_VEC_ELT (keys, i, sval) { if (multiline) pp_string (pp, " "); else if (!first) pp_string (pp, ", "); first = false; - const svalue *sval = (*iter).first; - pp_pointer (pp, sval); - pp_string (pp, ": "); + if (!flag_dump_noaddr) + { + pp_pointer (pp, sval); + pp_string (pp, ": "); + } sval->dump_to_pp (pp, simple); - entry_t e = (*iter).second; + entry_t e = *const_cast (m_map).get (sval); pp_string (pp, ": "); e.m_state->dump_to_pp (pp); if (model) @@ -916,6 +924,7 @@ program_state::prune_for_point (exploded_graph &eg, auto_vec ssa_name_regs; new_state.m_region_model->get_ssa_name_regions_for_current_frame (&ssa_name_regs); + ssa_name_regs.qsort (region::cmp_ptr_ptr); unsigned i; const decl_region *reg; FOR_EACH_VEC_ELT (ssa_name_regs, i, reg) @@ -1032,18 +1041,26 @@ program_state::validate (const extrinsic_state &ext_state) const static void log_set_of_svalues (logger *logger, const char *name, - const svalue_set &set) + const svalue_set &set) { logger->log (name); logger->inc_indent (); + auto_vec sval_vecs (set.elements ()); for (svalue_set::iterator iter = set.begin (); iter != set.end (); ++iter) + sval_vecs.quick_push (*iter); + sval_vecs.qsort (svalue::cmp_ptr_ptr); + unsigned i; + const svalue *sval; + FOR_EACH_VEC_ELT (sval_vecs, i, sval) { logger->start_log_line (); pretty_printer *pp = logger->get_printer (); - const svalue *sval = (*iter); - pp_pointer (pp, sval); - pp_string (pp, ": "); + if (!flag_dump_noaddr) + { + pp_pointer (pp, sval); + pp_string (pp, ": "); + } sval->dump_to_pp (pp, false); logger->end_log_line (); } diff --git a/gcc/analyzer/region-model-manager.cc b/gcc/analyzer/region-model-manager.cc index 8dd3ad0020a..f7fa33b028c 100644 --- a/gcc/analyzer/region-model-manager.cc +++ b/gcc/analyzer/region-model-manager.cc @@ -1033,13 +1033,19 @@ log_uniq_map (logger *logger, bool show_objs, const char *title, const hash_map &uniq_map) { logger->log (" # %s: %li", title, uniq_map.elements ()); - if (show_objs) - for (typename hash_map::iterator iter = uniq_map.begin (); - iter != uniq_map.end (); ++iter) - { - T *managed_obj = (*iter).second; - log_managed_object (logger, managed_obj); - } + if (!show_objs) + return; + auto_vec vec_objs (uniq_map.elements ()); + for (typename hash_map::iterator iter = uniq_map.begin (); + iter != uniq_map.end (); ++iter) + vec_objs.quick_push ((*iter).second); + + vec_objs.qsort (T::cmp_ptr_ptr); + + unsigned i; + const T *obj; + FOR_EACH_VEC_ELT (vec_objs, i, obj) + log_managed_object (logger, obj); } /* Dump the number of objects that were managed by MAP to LOGGER. @@ -1051,13 +1057,20 @@ log_uniq_map (logger *logger, bool show_objs, const char *title, const consolidation_map &map) { logger->log (" # %s: %li", title, map.elements ()); - if (show_objs) - for (typename consolidation_map::iterator iter = map.begin (); - iter != map.end (); ++iter) - { - T *managed_obj = (*iter).second; - log_managed_object (logger, managed_obj); - } + if (!show_objs) + return; + + auto_vec vec_objs (map.elements ()); + for (typename consolidation_map::iterator iter = map.begin (); + iter != map.end (); ++iter) + vec_objs.quick_push ((*iter).second); + + vec_objs.qsort (T::cmp_ptr_ptr); + + unsigned i; + const T *obj; + FOR_EACH_VEC_ELT (vec_objs, i, obj) + log_managed_object (logger, obj); } /* Dump the number of objects of each class that were managed by this diff --git a/gcc/analyzer/region-model-reachability.cc b/gcc/analyzer/region-model-reachability.cc index 3a6b312a8df..52525e1144b 100644 --- a/gcc/analyzer/region-model-reachability.cc +++ b/gcc/analyzer/region-model-reachability.cc @@ -227,6 +227,29 @@ reachable_regions::mark_escaped_clusters (region_model_context *ctxt) } } +/* Dump SET to PP, sorting it to avoid churn when comparing dumps. */ + +template +static void +dump_set (const hash_set &set, pretty_printer *pp) +{ + auto_vec elements (set.elements ()); + for (typename hash_set::iterator iter = set.begin (); + iter != set.end (); ++iter) + elements.quick_push (*iter); + + elements.qsort (T::cmp_ptr_ptr); + + unsigned i; + const T *element; + FOR_EACH_VEC_ELT (elements, i, element) + { + pp_string (pp, " "); + element->dump_to_pp (pp, true); + pp_newline (pp); + } +} + /* Dump a multiline representation of this object to PP. */ void @@ -234,40 +257,19 @@ reachable_regions::dump_to_pp (pretty_printer *pp) const { pp_string (pp, "reachable clusters: "); pp_newline (pp); - for (hash_set::iterator iter = m_reachable_base_regs.begin (); - iter != m_reachable_base_regs.end (); ++iter) - { - pp_string (pp, " "); - (*iter)->dump_to_pp (pp, true); - pp_newline (pp); - } + dump_set (m_reachable_base_regs, pp); + pp_string (pp, "mutable clusters: "); pp_newline (pp); - for (hash_set::iterator iter = m_mutable_base_regs.begin (); - iter != m_mutable_base_regs.end (); ++iter) - { - pp_string (pp, " "); - (*iter)->dump_to_pp (pp, true); - pp_newline (pp); - } + dump_set (m_mutable_base_regs, pp); + pp_string (pp, "reachable svals: "); pp_newline (pp); - for (svalue_set::iterator iter = m_reachable_svals.begin (); - iter != m_reachable_svals.end (); ++iter) - { - pp_string (pp, " "); - (*iter)->dump_to_pp (pp, true); - pp_newline (pp); - } + dump_set (m_reachable_svals, pp); + pp_string (pp, "mutable svals: "); pp_newline (pp); - for (svalue_set::iterator iter = m_mutable_svals.begin (); - iter != m_mutable_svals.end (); ++iter) - { - pp_string (pp, " "); - (*iter)->dump_to_pp (pp, true); - pp_newline (pp); - } + dump_set (m_mutable_svals, pp); } /* Dump a multiline representation of this object to stderr. */ diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h index 3298d05ffda..a67d6f4336f 100644 --- a/gcc/analyzer/region-model.h +++ b/gcc/analyzer/region-model.h @@ -300,6 +300,9 @@ public: virtual bool implicitly_live_p (const svalue_set &live_svalues, const region_model *model) const; + static int cmp_ptr (const svalue *, const svalue *); + static int cmp_ptr_ptr (const void *, const void *); + protected: svalue (complexity c, tree type) : m_complexity (c), m_type (type) @@ -552,6 +555,8 @@ struct setjmp_record hstate->add_ptr (m_setjmp_call); } + static int cmp (const setjmp_record &rec1, const setjmp_record &rec2); + const exploded_node *m_enode; const gcall *m_setjmp_call; }; @@ -987,6 +992,8 @@ public: void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE; void accept (visitor *v) const FINAL OVERRIDE; + const char *get_name () const { return m_name; } + private: const char *m_name; }; @@ -1078,6 +1085,7 @@ public: void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE; void accept (visitor *v) const FINAL OVERRIDE; + const function_point &get_point () const { return m_point; } const svalue *get_base_svalue () const { return m_base_sval; } const svalue *get_iter_svalue () const { return m_iter_sval; } @@ -1172,6 +1180,8 @@ public: void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE; void accept (visitor *v) const FINAL OVERRIDE; + const binding_map &get_map () const { return m_map; } + iterator_t begin () const { return m_map.begin (); } iterator_t end () const { return m_map.end (); } @@ -1280,6 +1290,9 @@ public: void dump_to_pp (pretty_printer *pp, bool simple) const FINAL OVERRIDE; void accept (visitor *v) const FINAL OVERRIDE; + const gimple *get_stmt () const { return m_stmt; } + const region *get_id_region () const { return m_id_reg; } + private: const gimple *m_stmt; const region *m_id_reg; @@ -1418,7 +1431,7 @@ public: bool non_null_p () const; - static int cmp_ptrs (const void *, const void *); + static int cmp_ptr_ptr (const void *, const void *); region_offset get_offset () const; bool get_byte_size (byte_size_t *out) const; diff --git a/gcc/analyzer/region.cc b/gcc/analyzer/region.cc index adf0e2c3ce3..3a88a5fbc67 100644 --- a/gcc/analyzer/region.cc +++ b/gcc/analyzer/region.cc @@ -517,10 +517,11 @@ region::region (complexity c, unsigned id, const region *parent, tree type) gcc_assert (type == NULL_TREE || TYPE_P (type)); } -/* Comparator for regions, using their IDs to order them. */ +/* Comparator for use by vec::qsort, + using their IDs to order them. */ int -region::cmp_ptrs (const void *p1, const void *p2) +region::cmp_ptr_ptr (const void *p1, const void *p2) { const region * const *reg1 = (const region * const *)p1; const region * const *reg2 = (const region * const *)p2; diff --git a/gcc/analyzer/state-purge.cc b/gcc/analyzer/state-purge.cc index e4942a692fa..418d80c608b 100644 --- a/gcc/analyzer/state-purge.cc +++ b/gcc/analyzer/state-purge.cc @@ -209,13 +209,21 @@ state_purge_per_ssa_name::state_purge_per_ssa_name (const state_purge_map &map, if (map.get_logger ()) { map.log ("%qE in %qD is needed to process:", name, fun->decl); + /* Log m_points_needing_name, sorting it to avoid churn when comparing + dumps. */ + auto_vec points; for (point_set_t::iterator iter = m_points_needing_name.begin (); iter != m_points_needing_name.end (); ++iter) + points.safe_push (*iter); + points.qsort (function_point::cmp_ptr); + unsigned i; + function_point *point; + FOR_EACH_VEC_ELT (points, i, point) { map.start_log_line (); map.get_logger ()->log_partial (" point: "); - (*iter).print (map.get_logger ()->get_printer (), format (false)); + point->print (map.get_logger ()->get_printer (), format (false)); map.end_log_line (); } } diff --git a/gcc/analyzer/store.cc b/gcc/analyzer/store.cc index 7e91addd035..05dd47d94a1 100644 --- a/gcc/analyzer/store.cc +++ b/gcc/analyzer/store.cc @@ -208,6 +208,23 @@ concrete_binding::overlaps_p (const concrete_binding &other) const return false; } +/* Comparator for use by vec::qsort. */ + +int +concrete_binding::cmp_ptr_ptr (const void *p1, const void *p2) +{ + const concrete_binding *b1 = *(const concrete_binding * const *)p1; + const concrete_binding *b2 = *(const concrete_binding * const *)p2; + + if (int kind_cmp = b1->get_kind () - b2->get_kind ()) + return kind_cmp; + + if (int start_cmp = wi::cmps (b1->m_start_bit_offset, b2->m_start_bit_offset)) + return start_cmp; + + return wi::cmpu (b1->m_size_in_bits, b2->m_size_in_bits); +} + /* class symbolic_binding : public binding_key. */ void @@ -218,6 +235,20 @@ symbolic_binding::dump_to_pp (pretty_printer *pp, bool simple) const m_region->dump_to_pp (pp, simple); } +/* Comparator for use by vec::qsort. */ + +int +symbolic_binding::cmp_ptr_ptr (const void *p1, const void *p2) +{ + const symbolic_binding *b1 = *(const symbolic_binding * const *)p1; + const symbolic_binding *b2 = *(const symbolic_binding * const *)p2; + + if (int kind_cmp = b1->get_kind () - b2->get_kind ()) + return kind_cmp; + + return region::cmp_ids (b1->get_region (), b2->get_region ()); +} + /* The store is oblivious to the types of the svalues bound within it: any type can get bound at any location. Simplify any casts before binding. @@ -409,6 +440,40 @@ binding_map::to_json () const return map_obj; } +/* Comparator for imposing an order on binding_maps. */ + +int +binding_map::cmp (const binding_map &map1, const binding_map &map2) +{ + if (int count_cmp = map1.elements () - map2.elements ()) + return count_cmp; + + auto_vec keys1 (map1.elements ()); + for (map_t::iterator iter = map1.begin (); + iter != map1.end (); ++iter) + keys1.quick_push ((*iter).first); + keys1.qsort (binding_key::cmp_ptrs); + + auto_vec keys2 (map2.elements ()); + for (map_t::iterator iter = map2.begin (); + iter != map2.end (); ++iter) + keys2.quick_push ((*iter).first); + keys2.qsort (binding_key::cmp_ptrs); + + for (size_t i = 0; i < keys1.length (); i++) + { + const binding_key *k1 = keys1[i]; + const binding_key *k2 = keys2[i]; + if (int key_cmp = binding_key::cmp (k1, k2)) + return key_cmp; + gcc_assert (k1 == k2); + if (int sval_cmp = svalue::cmp_ptr (map1.get (k1), map2.get (k2))) + return sval_cmp; + } + + return 0; +} + /* Get the child region of PARENT_REG based upon INDEX within a CONSTRUCTOR. */ @@ -1512,7 +1577,7 @@ get_sorted_parent_regions (auto_vec *out, out->safe_push (*iter); /* Sort OUT. */ - out->qsort (region::cmp_ptrs); + out->qsort (region::cmp_ptr_ptr); } /* Dump a representation of this store to PP, using SIMPLE to control how @@ -1532,7 +1597,7 @@ store::dump_to_pp (pretty_printer *pp, bool simple, bool multiline, const region *base_reg = (*iter).first; base_regions.safe_push (base_reg); } - base_regions.qsort (region::cmp_ptrs); + base_regions.qsort (region::cmp_ptr_ptr); /* Gather clusters, organize by parent region, so that we can group together locals, globals, etc. */ @@ -1653,7 +1718,7 @@ store::to_json () const const region *base_reg = (*iter).first; base_regions.safe_push (base_reg); } - base_regions.qsort (region::cmp_ptrs); + base_regions.qsort (region::cmp_ptr_ptr); /* Gather clusters, organize by parent region, so that we can group together locals, globals, etc. */ @@ -1991,10 +2056,19 @@ store::can_merge_p (const store *store_a, const store *store_b, base_regions.add (base_reg_b); } + /* Sort the base regions before considering them. This ought not to + affect the results, but can affect which types UNKNOWN_REGIONs are + created for in a run; sorting them thus avoids minor differences + in logfiles. */ + auto_vec vec_base_regions (base_regions.elements ()); for (hash_set::iterator iter = base_regions.begin (); iter != base_regions.end (); ++iter) + vec_base_regions.quick_push (*iter); + vec_base_regions.qsort (region::cmp_ptr_ptr); + unsigned i; + const region *base_reg; + FOR_EACH_VEC_ELT (vec_base_regions, i, base_reg) { - const region *base_reg = *iter; const binding_cluster *cluster_a = store_a->get_cluster (base_reg); const binding_cluster *cluster_b = store_b->get_cluster (base_reg); /* At least one of cluster_a and cluster_b must be non-NULL. */ diff --git a/gcc/analyzer/store.h b/gcc/analyzer/store.h index 0f4e7ab2a56..466c1830c0f 100644 --- a/gcc/analyzer/store.h +++ b/gcc/analyzer/store.h @@ -237,6 +237,8 @@ public: bool overlaps_p (const concrete_binding &other) const; + static int cmp_ptr_ptr (const void *, const void *); + private: bit_offset_t m_start_bit_offset; bit_size_t m_size_in_bits; @@ -282,6 +284,8 @@ public: const region *get_region () const { return m_region; } + static int cmp_ptr_ptr (const void *, const void *); + private: const region *m_region; }; @@ -346,6 +350,8 @@ public: bool apply_ctor_to_region (const region *parent_reg, tree ctor, region_model_manager *mgr); + static int cmp (const binding_map &map1, const binding_map &map2); + private: bool apply_ctor_val_to_range (const region *parent_reg, region_model_manager *mgr, diff --git a/gcc/analyzer/supergraph.cc b/gcc/analyzer/supergraph.cc index 735c4a30e09..37f143c6fca 100644 --- a/gcc/analyzer/supergraph.cc +++ b/gcc/analyzer/supergraph.cc @@ -90,7 +90,8 @@ supergraph_call_edge (function *fun, gimple *stmt) /* supergraph's ctor. Walk the callgraph, building supernodes for each CFG basic block, splitting the basic blocks at callsites. Join together the supernodes with interprocedural and intraprocedural - superedges as appropriate. */ + superedges as appropriate. + Assign UIDs to the gimple stmts. */ supergraph::supergraph (logger *logger) { @@ -98,8 +99,10 @@ supergraph::supergraph (logger *logger) LOG_FUNC (logger); - /* First pass: make supernodes. */ + /* First pass: make supernodes (and assign UIDs to the gimple stmts). */ { + unsigned next_uid = 0; + /* Sort the cgraph_nodes? */ cgraph_node *node; FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) @@ -124,6 +127,7 @@ supergraph::supergraph (logger *logger) { gimple *stmt = gsi_stmt (gpi); m_stmt_to_node_t.put (stmt, node_for_stmts); + stmt->uid = next_uid++; } /* Append statements from BB to the current supernode, splitting @@ -135,6 +139,7 @@ supergraph::supergraph (logger *logger) gimple *stmt = gsi_stmt (gsi); node_for_stmts->m_stmts.safe_push (stmt); m_stmt_to_node_t.put (stmt, node_for_stmts); + stmt->uid = next_uid++; if (cgraph_edge *edge = supergraph_call_edge (fun, stmt)) { m_cgraph_edge_to_caller_prev_node.put(edge, node_for_stmts); diff --git a/gcc/analyzer/svalue.cc b/gcc/analyzer/svalue.cc index ae3b6783e9c..8eece134e10 100644 --- a/gcc/analyzer/svalue.cc +++ b/gcc/analyzer/svalue.cc @@ -298,6 +298,211 @@ svalue::implicitly_live_p (const svalue_set &, const region_model *) const return false; } +/* Comparator for imposing a deterministic order on constants that are + of the same type. */ + +static int +cmp_cst (const_tree cst1, const_tree cst2) +{ + gcc_assert (TREE_TYPE (cst1) == TREE_TYPE (cst2)); + gcc_assert (TREE_CODE (cst1) == TREE_CODE (cst2)); + switch (TREE_CODE (cst1)) + { + default: + gcc_unreachable (); + case INTEGER_CST: + return tree_int_cst_compare (cst1, cst2); + case STRING_CST: + return strcmp (TREE_STRING_POINTER (cst1), + TREE_STRING_POINTER (cst2)); + case REAL_CST: + /* Impose an arbitrary but deterministic order. */ + return memcmp (TREE_REAL_CST_PTR (cst1), + TREE_REAL_CST_PTR (cst2), + sizeof (real_value)); + case VECTOR_CST: + if (int cmp_log2_npatterns + = ((int)VECTOR_CST_LOG2_NPATTERNS (cst1) + - (int)VECTOR_CST_LOG2_NPATTERNS (cst2))) + return cmp_log2_npatterns; + if (int cmp_nelts_per_pattern + = ((int)VECTOR_CST_NELTS_PER_PATTERN (cst1) + - (int)VECTOR_CST_NELTS_PER_PATTERN (cst2))) + return cmp_nelts_per_pattern; + unsigned encoded_nelts = vector_cst_encoded_nelts (cst1); + for (unsigned i = 0; i < encoded_nelts; i++) + if (int el_cmp = cmp_cst (VECTOR_CST_ENCODED_ELT (cst1, i), + VECTOR_CST_ENCODED_ELT (cst2, i))) + return el_cmp; + return 0; + } +} + +/* Comparator for imposing a deterministic order on svalues. */ + +int +svalue::cmp_ptr (const svalue *sval1, const svalue *sval2) +{ + if (sval1 == sval2) + return 0; + if (int cmp_kind = sval1->get_kind () - sval2->get_kind ()) + return cmp_kind; + int t1 = sval1->get_type () ? TYPE_UID (sval1->get_type ()) : -1; + int t2 = sval2->get_type () ? TYPE_UID (sval2->get_type ()) : -1; + if (int cmp_type = t1 - t2) + return cmp_type; + switch (sval1->get_kind ()) + { + default: + gcc_unreachable (); + case SK_REGION: + { + const region_svalue *region_sval1 = (const region_svalue *)sval1; + const region_svalue *region_sval2 = (const region_svalue *)sval2; + return region::cmp_ids (region_sval1->get_pointee (), + region_sval2->get_pointee ()); + } + break; + case SK_CONSTANT: + { + const constant_svalue *constant_sval1 = (const constant_svalue *)sval1; + const constant_svalue *constant_sval2 = (const constant_svalue *)sval2; + const_tree cst1 = constant_sval1->get_constant (); + const_tree cst2 = constant_sval2->get_constant (); + return cmp_cst (cst1, cst2); + } + break; + case SK_UNKNOWN: + { + gcc_assert (sval1 == sval2); + return 0; + } + break; + case SK_POISONED: + { + const poisoned_svalue *poisoned_sval1 = (const poisoned_svalue *)sval1; + const poisoned_svalue *poisoned_sval2 = (const poisoned_svalue *)sval2; + return (poisoned_sval1->get_poison_kind () + - poisoned_sval2->get_poison_kind ()); + } + break; + case SK_SETJMP: + { + const setjmp_svalue *setjmp_sval1 = (const setjmp_svalue *)sval1; + const setjmp_svalue *setjmp_sval2 = (const setjmp_svalue *)sval2; + const setjmp_record &rec1 = setjmp_sval1->get_setjmp_record (); + const setjmp_record &rec2 = setjmp_sval2->get_setjmp_record (); + return setjmp_record::cmp (rec1, rec2); + } + break; + case SK_INITIAL: + { + const initial_svalue *initial_sval1 = (const initial_svalue *)sval1; + const initial_svalue *initial_sval2 = (const initial_svalue *)sval2; + return region::cmp_ids (initial_sval1->get_region (), + initial_sval2->get_region ()); + } + break; + case SK_UNARYOP: + { + const unaryop_svalue *unaryop_sval1 = (const unaryop_svalue *)sval1; + const unaryop_svalue *unaryop_sval2 = (const unaryop_svalue *)sval2; + if (int op_cmp = unaryop_sval1->get_op () - unaryop_sval2->get_op ()) + return op_cmp; + return svalue::cmp_ptr (unaryop_sval1->get_arg (), + unaryop_sval2->get_arg ()); + } + break; + case SK_BINOP: + { + const binop_svalue *binop_sval1 = (const binop_svalue *)sval1; + const binop_svalue *binop_sval2 = (const binop_svalue *)sval2; + if (int op_cmp = binop_sval1->get_op () - binop_sval2->get_op ()) + return op_cmp; + if (int arg0_cmp = svalue::cmp_ptr (binop_sval1->get_arg0 (), + binop_sval2->get_arg0 ())) + return arg0_cmp; + return svalue::cmp_ptr (binop_sval1->get_arg1 (), + binop_sval2->get_arg1 ()); + } + break; + case SK_SUB: + { + const sub_svalue *sub_sval1 = (const sub_svalue *)sval1; + const sub_svalue *sub_sval2 = (const sub_svalue *)sval2; + if (int parent_cmp = svalue::cmp_ptr (sub_sval1->get_parent (), + sub_sval2->get_parent ())) + return parent_cmp; + return region::cmp_ids (sub_sval1->get_subregion (), + sub_sval2->get_subregion ()); + } + break; + case SK_UNMERGEABLE: + { + const unmergeable_svalue *unmergeable_sval1 + = (const unmergeable_svalue *)sval1; + const unmergeable_svalue *unmergeable_sval2 + = (const unmergeable_svalue *)sval2; + return svalue::cmp_ptr (unmergeable_sval1->get_arg (), + unmergeable_sval2->get_arg ()); + } + break; + case SK_PLACEHOLDER: + { + const placeholder_svalue *placeholder_sval1 + = (const placeholder_svalue *)sval1; + const placeholder_svalue *placeholder_sval2 + = (const placeholder_svalue *)sval2; + return strcmp (placeholder_sval1->get_name (), + placeholder_sval2->get_name ()); + } + break; + case SK_WIDENING: + { + const widening_svalue *widening_sval1 = (const widening_svalue *)sval1; + const widening_svalue *widening_sval2 = (const widening_svalue *)sval2; + if (int point_cmp = function_point::cmp (widening_sval1->get_point (), + widening_sval2->get_point ())) + return point_cmp; + if (int base_cmp = svalue::cmp_ptr (widening_sval1->get_base_svalue (), + widening_sval2->get_base_svalue ())) + return base_cmp; + return svalue::cmp_ptr (widening_sval1->get_iter_svalue (), + widening_sval2->get_iter_svalue ()); + } + break; + case SK_COMPOUND: + { + const compound_svalue *compound_sval1 = (const compound_svalue *)sval1; + const compound_svalue *compound_sval2 = (const compound_svalue *)sval2; + return binding_map::cmp (compound_sval1->get_map (), + compound_sval2->get_map ()); + } + break; + case SK_CONJURED: + { + const conjured_svalue *conjured_sval1 = (const conjured_svalue *)sval1; + const conjured_svalue *conjured_sval2 = (const conjured_svalue *)sval2; + if (int stmt_cmp = (conjured_sval1->get_stmt ()->uid + - conjured_sval2->get_stmt ()->uid)) + return stmt_cmp; + return region::cmp_ids (conjured_sval1->get_id_region (), + conjured_sval2->get_id_region ()); + } + break; + } +} + +/* Comparator for use by vec::qsort. */ + +int +svalue::cmp_ptr_ptr (const void *p1, const void *p2) +{ + const svalue *sval1 = *(const svalue * const *)p1; + const svalue *sval2 = *(const svalue * const *)p2; + return cmp_ptr (sval1, sval2); +} + /* class region_svalue : public svalue. */ /* Implementation of svalue::dump_to_pp vfunc for region_svalue. */ -- 2.30.2