From patchwork Tue Jun 15 13:38:27 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: David Malcolm X-Patchwork-Id: 1492216 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=MHizdctX; dkim-atps=neutral Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4G48Yt2SyJz9sW6 for ; Tue, 15 Jun 2021 23:39:30 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0A5B6393BC37 for ; Tue, 15 Jun 2021 13:39:27 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 0A5B6393BC37 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1623764367; bh=qZyIHMmUUBNxXb3znjMOCOFaKgbX5n+00XIBVRr83Hs=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=MHizdctXYe9QHrhJ2ljuPkrfkOuwWBrSirVE5JCNpksvMFYHz8HfIj1OWmakJkEFV lZogERS8/Gld4KLxdkedIzUlvZYbpqs82N2rcGsbi2DqdSCs8Xlmwo9v9vYoIoix5L ItIsOq00+K/TmiH8z0rX+fZr2lH5/K5xCWaPEUgQ= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTP id E15F83894C05 for ; Tue, 15 Jun 2021 13:38:32 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org E15F83894C05 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-594-B_KSGBEsOvqD3adn0rM8mQ-1; Tue, 15 Jun 2021 09:38:30 -0400 X-MC-Unique: B_KSGBEsOvqD3adn0rM8mQ-1 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id CF6FA80293C for ; Tue, 15 Jun 2021 13:38:29 +0000 (UTC) Received: from t14s.localdomain.com (ovpn-112-247.phx2.redhat.com [10.3.112.247]) by smtp.corp.redhat.com (Postfix) with ESMTP id 7785219813; Tue, 15 Jun 2021 13:38:29 +0000 (UTC) To: gcc-patches@gcc.gnu.org Subject: [committed] analyzer: add class region_to_value_map Date: Tue, 15 Jun 2021 09:38:27 -0400 Message-Id: <20210615133827.347951-1-dmalcolm@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.11 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.4 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: David Malcolm via Gcc-patches From: David Malcolm Reply-To: David Malcolm Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" Add a class for associating symbolic values with regions, for use initially for recording the sizes of dynamically-allocated regions, though this also could potentially be used for e.g. tracking strlen() values. Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu. Pushed to trunk as d726a57b993e00294891e2a05d5868c89bb75b76. gcc/analyzer/ChangeLog: * region-model.cc (region_to_value_map::operator=): New. (region_to_value_map::operator==): New. (region_to_value_map::dump_to_pp): New. (region_to_value_map::dump): New. (region_to_value_map::can_merge_with_p): New. * region-model.h (class region_to_value_map): New class. Signed-off-by: David Malcolm --- gcc/analyzer/region-model.cc | 110 +++++++++++++++++++++++++++++++++++ gcc/analyzer/region-model.h | 45 ++++++++++++++ 2 files changed, 155 insertions(+) diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc index 4b9620d9887..43f991a2a29 100644 --- a/gcc/analyzer/region-model.cc +++ b/gcc/analyzer/region-model.cc @@ -110,6 +110,116 @@ print_quoted_type (pretty_printer *pp, tree t) pp_end_quote (pp, pp_show_color (pp)); } +/* class region_to_value_map. */ + +/* Assignment operator for region_to_value_map. */ + +region_to_value_map & +region_to_value_map::operator= (const region_to_value_map &other) +{ + m_hash_map.empty (); + for (auto iter : other.m_hash_map) + { + const region *reg = iter.first; + const svalue *sval = iter.second; + m_hash_map.put (reg, sval); + } + return *this; +} + +/* Equality operator for region_to_value_map. */ + +bool +region_to_value_map::operator== (const region_to_value_map &other) const +{ + if (m_hash_map.elements () != other.m_hash_map.elements ()) + return false; + + for (auto iter : *this) + { + const region *reg = iter.first; + const svalue *sval = iter.second; + const svalue * const *other_slot = other.get (reg); + if (other_slot == NULL) + return false; + if (sval != *other_slot) + return false; + } + + return true; +} + +/* Dump this object to PP. */ + +void +region_to_value_map::dump_to_pp (pretty_printer *pp, bool simple, + bool multiline) const +{ + auto_vec regs; + for (iterator iter = begin (); iter != end (); ++iter) + regs.safe_push ((*iter).first); + regs.qsort (region::cmp_ptr_ptr); + if (multiline) + pp_newline (pp); + else + pp_string (pp, " {"); + unsigned i; + const region *reg; + FOR_EACH_VEC_ELT (regs, i, reg) + { + if (multiline) + pp_string (pp, " "); + else if (i > 0) + pp_string (pp, ", "); + reg->dump_to_pp (pp, simple); + pp_string (pp, ": "); + const svalue *sval = *get (reg); + sval->dump_to_pp (pp, true); + if (multiline) + pp_newline (pp); + } + if (!multiline) + pp_string (pp, "}"); +} + +/* Dump this object to stderr. */ + +DEBUG_FUNCTION void +region_to_value_map::dump (bool simple) const +{ + pretty_printer pp; + pp_format_decoder (&pp) = default_tree_printer; + pp_show_color (&pp) = pp_show_color (global_dc->printer); + pp.buffer->stream = stderr; + dump_to_pp (&pp, simple, true); + pp_newline (&pp); + pp_flush (&pp); +} + + +/* Attempt to merge THIS with OTHER, writing the result + to OUT. + + For now, write (region, value) mappings that are in common between THIS + and OTHER to OUT, effectively taking the intersection, rather than + rejecting differences. */ + +bool +region_to_value_map::can_merge_with_p (const region_to_value_map &other, + region_to_value_map *out) const +{ + for (auto iter : *this) + { + const region *iter_reg = iter.first; + const svalue *iter_sval = iter.second; + const svalue * const * other_slot = other.get (iter_reg); + if (other_slot) + if (iter_sval == *other_slot) + out->put (iter_reg, iter_sval); + } + return true; +} + /* class region_model. */ /* Ctor for region_model: construct an "empty" model. */ diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h index e251a5b245c..0afcb8635a9 100644 --- a/gcc/analyzer/region-model.h +++ b/gcc/analyzer/region-model.h @@ -128,6 +128,51 @@ one_way_id_map::update (T *id) const *id = get_dst_for_src (*id); } +/* A mapping from region to svalue for use when tracking state. */ + +class region_to_value_map +{ +public: + typedef hash_map hash_map_t; + typedef hash_map_t::iterator iterator; + + region_to_value_map () : m_hash_map () {} + region_to_value_map (const region_to_value_map &other) + : m_hash_map (other.m_hash_map) {} + region_to_value_map &operator= (const region_to_value_map &other); + + bool operator== (const region_to_value_map &other) const; + bool operator!= (const region_to_value_map &other) const + { + return !(*this == other); + } + + iterator begin () const { return m_hash_map.begin (); } + iterator end () const { return m_hash_map.end (); } + + const svalue * const *get (const region *reg) const + { + return const_cast (m_hash_map).get (reg); + } + void put (const region *reg, const svalue *sval) + { + m_hash_map.put (reg, sval); + } + void remove (const region *reg) + { + m_hash_map.remove (reg); + } + + void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const; + void dump (bool simple) const; + + bool can_merge_with_p (const region_to_value_map &other, + region_to_value_map *out) const; + +private: + hash_map_t m_hash_map; +}; + /* Various operations delete information from a region_model. This struct tracks how many of each kind of entity were purged (e.g.