From patchwork Sat Nov 16 01:23:27 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: David Malcolm X-Patchwork-Id: 1196032 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=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-513756-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="Jh+tNwXu"; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.b="jNcAlw1+"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 47FHdc620Vz9s7T for ; Sat, 16 Nov 2019 12:27:31 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:in-reply-to:references :content-type:content-transfer-encoding; q=dns; s=default; b=amn 589mnLW4Q5upQY1BpSB56QgskVlisQuiwoNijT1+hx4GrqwoBg4PblvTJ8QCLRJS dUye3OAHGqbfB8xlYbfvodvIivEpDn0FWfDCicySTx4sxWlcv1KRVpGCWtBPnOcX mgQjofU+A/+EHcxQEFAbzKUTAAxVuKOFufP6Xkfw= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:in-reply-to:references :content-type:content-transfer-encoding; s=default; bh=eaTqpVvF+ 8OTllHjMPxvpZvZN24=; b=Jh+tNwXuQl9V/JQvPPc/inSPLQh1uPRd3mXKCwVrk L1w2FijPyKSfMyGmPTBRlx4kvu5ecOMgnAAQLbM6sqSNf1hBBqZYa6/epU95kxp0 xkkV/4W7ewxgxvR27hDcXdGqi92Tz7zfgiw2nnMpHhbr/nL83NfSa/5Sfy78MEpM YY= Received: (qmail 81178 invoked by alias); 16 Nov 2019 01:21:20 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 62306 invoked by uid 89); 16 Nov 2019 01:18:18 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-22.2 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT autolearn=ham version=3.3.1 spammy= X-HELO: us-smtp-delivery-1.mimecast.com Received: from us-smtp-1.mimecast.com (HELO us-smtp-delivery-1.mimecast.com) (205.139.110.61) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sat, 16 Nov 2019 01:17:58 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1573867077; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=0sTZr/jQHQ1SNoEaVkblGqqD5xG+8nIRcRINs1muD2I=; b=jNcAlw1+q1ePzxYSvUGu2AksVKVaX9JKSNXVaJxsgXIlzq8AYqxXKKIwWDJDOJT4+zOnFZ 9paDuhlEqBBU3ugG6cBZWN66AtEX54KhUmWW4DIrgclcM3ZQJU8pcw1MtfKHBaQA1eCHIZ 2EHySANUfQcJMwEuZhPclGoqF7Ukr+s= 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-426-Uu9xGxebOOCXjfAzc0zIGA-1; Fri, 15 Nov 2019 20:17:55 -0500 Received: from smtp.corp.redhat.com (int-mx07.intmail.prod.int.phx2.redhat.com [10.5.11.22]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 08ABE800052 for ; Sat, 16 Nov 2019 01:17:55 +0000 (UTC) Received: from c64.redhat.com (ovpn-112-32.phx2.redhat.com [10.3.112.32]) by smtp.corp.redhat.com (Postfix) with ESMTP id 1BA6310246FB; Sat, 16 Nov 2019 01:17:53 +0000 (UTC) From: David Malcolm To: gcc-patches@gcc.gnu.org Cc: David Malcolm Subject: [PATCH 40/49] analyzer: new files: call-string.{cc|h} Date: Fri, 15 Nov 2019 20:23:27 -0500 Message-Id: <1573867416-55618-41-git-send-email-dmalcolm@redhat.com> In-Reply-To: <1573867416-55618-1-git-send-email-dmalcolm@redhat.com> References: <1573867416-55618-1-git-send-email-dmalcolm@redhat.com> X-Mimecast-Spam-Score: 0 X-IsSubscribed: yes This patch adds call_string, a class for representing the call stacks at a program_point, so that we can ensure that paths through the code are interprocedurally valid. gcc/ChangeLog: * analyzer/call-string.cc: New file. * analyzer/call-string.h: New file. --- gcc/analyzer/call-string.cc | 201 ++++++++++++++++++++++++++++++++++++++++++++ gcc/analyzer/call-string.h | 74 ++++++++++++++++ 2 files changed, 275 insertions(+) create mode 100644 gcc/analyzer/call-string.cc create mode 100644 gcc/analyzer/call-string.h diff --git a/gcc/analyzer/call-string.cc b/gcc/analyzer/call-string.cc new file mode 100644 index 0000000..796b5e7 --- /dev/null +++ b/gcc/analyzer/call-string.cc @@ -0,0 +1,201 @@ +/* Call stacks at program points. + Copyright (C) 2019 Free Software Foundation, Inc. + Contributed by David Malcolm . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "gcc-plugin.h" +#include "system.h" +#include "coretypes.h" +#include "pretty-print.h" +#include "tree.h" +#include "analyzer/call-string.h" +#include "analyzer/supergraph.h" + +/* class call_string. */ + +/* call_string's copy ctor. */ + +call_string::call_string (const call_string &other) +: m_return_edges (other.m_return_edges.length ()) +{ + const return_superedge *e; + int i; + FOR_EACH_VEC_ELT (other.m_return_edges, i, e) + m_return_edges.quick_push (e); +} + +/* call_string's assignment operator. */ + +call_string& +call_string::operator= (const call_string &other) +{ + // would be much simpler if we could rely on vec<> assignment op + m_return_edges.truncate (0); + m_return_edges.reserve (other.m_return_edges.length (), true); + const return_superedge *e; + int i; + FOR_EACH_VEC_ELT (other.m_return_edges, i, e) + m_return_edges.quick_push (e); + return *this; +} + +/* call_string's equality operator. */ + +bool +call_string::operator== (const call_string &other) const +{ + if (m_return_edges.length () != other.m_return_edges.length ()) + return false; + const return_superedge *e; + int i; + FOR_EACH_VEC_ELT (m_return_edges, i, e) + if (e != other.m_return_edges[i]) + return false; + return true; +} + +/* Print this to PP. */ + +void +call_string::print (pretty_printer *pp) const +{ + pp_string (pp, "["); + + const return_superedge *e; + int i; + FOR_EACH_VEC_ELT (m_return_edges, i, e) + { + if (i > 0) + pp_string (pp, ", "); + pp_printf (pp, "(SN: %i -> SN: %i in %s)", + e->m_src->m_index, e->m_dest->m_index, + function_name (e->m_dest->m_fun)); + } + + pp_string (pp, "]"); +} + +/* Generate a hash value for this call_string. */ + +hashval_t +call_string::hash () const +{ + inchash::hash hstate; + int i; + const return_superedge *e; + FOR_EACH_VEC_ELT (m_return_edges, i, e) + hstate.add_ptr (e); + return hstate.end (); +} + +/* Push the return superedge for CALL_SEDGE onto the end of this + call_string. */ + +void +call_string::push_call (const supergraph &sg, + const call_superedge *call_sedge) +{ + gcc_assert (call_sedge); + const return_superedge *return_sedge = call_sedge->get_edge_for_return (sg); + gcc_assert (return_sedge); + m_return_edges.safe_push (return_sedge); +} + +/* Count the number of times the top-most call site appears in the + stack. */ + +int +call_string::calc_recursion_depth () const +{ + if (m_return_edges.is_empty ()) + return 0; + const return_superedge *top_return_sedge + = m_return_edges[m_return_edges.length () - 1]; + + int result = 0; + const return_superedge *e; + int i; + FOR_EACH_VEC_ELT (m_return_edges, i, e) + if (e == top_return_sedge) + ++result; + return result; +} + +/* Comparator for call strings. + Return negative if A is before B. + Return positive if B is after A. + Return 0 if they are equal. */ + +int +call_string::cmp (const call_string &a, + const call_string &b) +{ + int result = cmp_1 (a, b); + + /* Check that the ordering is symmetric */ +#if CHECKING_P + int reversed = cmp_1 (b, a); + gcc_assert (reversed == -result); +#endif + + /* We should only have 0 for equal pairs. */ + gcc_assert (result != 0 + || a == b); + + return result; +} + +/* Implementation of call_string::cmp. + This implements a version of lexicographical order. */ + +int +call_string::cmp_1 (const call_string &a, + const call_string &b) +{ + unsigned len_a = a.length (); + unsigned len_b = b.length (); + + unsigned i = 0; + while (1) + { + /* Consider index i; the strings have been equal up to it. */ + + /* Have both strings run out? */ + if (i >= len_a && i >= len_b) + return 0; + + /* Otherwise, has just one of the strings run out? */ + if (i >= len_a) + return 1; + if (i >= len_b) + return -1; + + /* Otherwise, compare the edges. */ + const return_superedge *edge_a = a[i]; + const return_superedge *edge_b = b[i]; + int src_cmp = edge_a->m_src->m_index - edge_b->m_src->m_index; + if (src_cmp) + return src_cmp; + int dest_cmp = edge_a->m_dest->m_index - edge_b->m_dest->m_index; + if (dest_cmp) + return dest_cmp; + i++; + // TODO: test coverage for this + } +} diff --git a/gcc/analyzer/call-string.h b/gcc/analyzer/call-string.h new file mode 100644 index 0000000..e5657e6 --- /dev/null +++ b/gcc/analyzer/call-string.h @@ -0,0 +1,74 @@ +/* Call stacks at program points. + Copyright (C) 2019 Free Software Foundation, Inc. + Contributed by David Malcolm . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#ifndef GCC_ANALYZER_CALL_STRING_H +#define GCC_ANALYZER_CALL_STRING_H + +class supergraph; +class call_superedge; +class return_superedge; + +/* A string of return_superedge pointers, representing a call stack + at a program point. + + This is used to ensure that we generate interprocedurally valid paths + i.e. that we return to the same callsite that called us. + + The class actually stores the return edges, rather than the call edges, + since that's what we need to compare against. */ + +class call_string +{ +public: + call_string () : m_return_edges () {} + call_string (const call_string &other); + call_string& operator= (const call_string &other); + + bool operator== (const call_string &other) const; + + void print (pretty_printer *pp) const; + + hashval_t hash () const; + + bool empty_p () const { return m_return_edges.is_empty (); } + + void push_call (const supergraph &sg, + const call_superedge *sedge); + const return_superedge *pop () { return m_return_edges.pop (); } + + int calc_recursion_depth () const; + + static int cmp (const call_string &a, + const call_string &b); + + unsigned length () const { return m_return_edges.length (); } + const return_superedge *operator[] (unsigned idx) const + { + return m_return_edges[idx]; + } + +private: + static int cmp_1 (const call_string &a, + const call_string &b); + + auto_vec m_return_edges; +}; + +#endif /* GCC_ANALYZER_CALL_STRING_H */