1 /* Call stacks at program points. 2 Copyright (C) 2019-2020 Free Software Foundation, Inc. 3 Contributed by David Malcolm <dmalcolm@redhat.com>. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it 8 under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 3, or (at your option) 10 any later version. 11 12 GCC is distributed in the hope that it will be useful, but 13 WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "pretty-print.h" 25 #include "tree.h" 26 #include "options.h" 27 #include "analyzer/call-string.h" 28 #include "ordered-hash-map.h" 29 #include "options.h" 30 #include "cgraph.h" 31 #include "function.h" 32 #include "cfg.h" 33 #include "basic-block.h" 34 #include "gimple.h" 35 #include "gimple-iterator.h" 36 #include "digraph.h" 37 #include "analyzer/supergraph.h" 38 39 #if ENABLE_ANALYZER 40 41 /* class call_string. */ 42 43 /* call_string's copy ctor. */ 44 45 call_string::call_string (const call_string &other) 46 : m_return_edges (other.m_return_edges.length ()) 47 { 48 const return_superedge *e; 49 int i; 50 FOR_EACH_VEC_ELT (other.m_return_edges, i, e) 51 m_return_edges.quick_push (e); 52 } 53 54 /* call_string's assignment operator. */ 55 56 call_string& 57 call_string::operator= (const call_string &other) 58 { 59 // would be much simpler if we could rely on vec<> assignment op 60 m_return_edges.truncate (0); 61 m_return_edges.reserve (other.m_return_edges.length (), true); 62 const return_superedge *e; 63 int i; 64 FOR_EACH_VEC_ELT (other.m_return_edges, i, e) 65 m_return_edges.quick_push (e); 66 return *this; 67 } 68 69 /* call_string's equality operator. */ 70 71 bool 72 call_string::operator== (const call_string &other) const 73 { 74 if (m_return_edges.length () != other.m_return_edges.length ()) 75 return false; 76 const return_superedge *e; 77 int i; 78 FOR_EACH_VEC_ELT (m_return_edges, i, e) 79 if (e != other.m_return_edges[i]) 80 return false; 81 return true; 82 } 83 84 /* Print this to PP. */ 85 86 void 87 call_string::print (pretty_printer *pp) const 88 { 89 pp_string (pp, "["); 90 91 const return_superedge *e; 92 int i; 93 FOR_EACH_VEC_ELT (m_return_edges, i, e) 94 { 95 if (i > 0) 96 pp_string (pp, ", "); 97 pp_printf (pp, "(SN: %i -> SN: %i in %s)", 98 e->m_src->m_index, e->m_dest->m_index, 99 function_name (e->m_dest->m_fun)); 100 } 101 102 pp_string (pp, "]"); 103 } 104 105 /* Generate a hash value for this call_string. */ 106 107 hashval_t 108 call_string::hash () const 109 { 110 inchash::hash hstate; 111 int i; 112 const return_superedge *e; 113 FOR_EACH_VEC_ELT (m_return_edges, i, e) 114 hstate.add_ptr (e); 115 return hstate.end (); 116 } 117 118 /* Push the return superedge for CALL_SEDGE onto the end of this 119 call_string. */ 120 121 void 122 call_string::push_call (const supergraph &sg, 123 const call_superedge *call_sedge) 124 { 125 gcc_assert (call_sedge); 126 const return_superedge *return_sedge = call_sedge->get_edge_for_return (sg); 127 gcc_assert (return_sedge); 128 m_return_edges.safe_push (return_sedge); 129 } 130 131 /* Count the number of times the top-most call site appears in the 132 stack. */ 133 134 int 135 call_string::calc_recursion_depth () const 136 { 137 if (m_return_edges.is_empty ()) 138 return 0; 139 const return_superedge *top_return_sedge 140 = m_return_edges[m_return_edges.length () - 1]; 141 142 int result = 0; 143 const return_superedge *e; 144 int i; 145 FOR_EACH_VEC_ELT (m_return_edges, i, e) 146 if (e == top_return_sedge) 147 ++result; 148 return result; 149 } 150 151 /* Comparator for call strings. 152 This implements a version of lexicographical order. 153 Return negative if A is before B. 154 Return positive if B is after A. 155 Return 0 if they are equal. */ 156 157 int 158 call_string::cmp (const call_string &a, 159 const call_string &b) 160 { 161 unsigned len_a = a.length (); 162 unsigned len_b = b.length (); 163 164 unsigned i = 0; 165 while (1) 166 { 167 /* Consider index i; the strings have been equal up to it. */ 168 169 /* Have both strings run out? */ 170 if (i >= len_a && i >= len_b) 171 return 0; 172 173 /* Otherwise, has just one of the strings run out? */ 174 if (i >= len_a) 175 return 1; 176 if (i >= len_b) 177 return -1; 178 179 /* Otherwise, compare the edges. */ 180 const return_superedge *edge_a = a[i]; 181 const return_superedge *edge_b = b[i]; 182 int src_cmp = edge_a->m_src->m_index - edge_b->m_src->m_index; 183 if (src_cmp) 184 return src_cmp; 185 int dest_cmp = edge_a->m_dest->m_index - edge_b->m_dest->m_index; 186 if (dest_cmp) 187 return dest_cmp; 188 i++; 189 // TODO: test coverage for this 190 } 191 } 192 193 /* Assert that this object is sane. */ 194 195 void 196 call_string::validate () const 197 { 198 /* Skip this in a release build. */ 199 #if !CHECKING_P 200 return; 201 #endif 202 203 /* Each entry's "caller" should be the "callee" of the previous entry. */ 204 const return_superedge *e; 205 int i; 206 FOR_EACH_VEC_ELT (m_return_edges, i, e) 207 if (i > 0) 208 gcc_assert (e->get_caller_function () 209 == m_return_edges[i - 1]->get_callee_function ()); 210 } 211 212 #endif /* #if ENABLE_ANALYZER */ 213