1 /* Classes for representing locations within the program. 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 #ifndef GCC_ANALYZER_PROGRAM_POINT_H 22 #define GCC_ANALYZER_PROGRAM_POINT_H 23 24 namespace ana { 25 26 class exploded_graph; 27 28 /* An enum for distinguishing the various kinds of program_point. */ 29 30 enum point_kind { 31 /* A "fake" node which has edges to all entrypoints. */ 32 PK_ORIGIN, 33 34 PK_BEFORE_SUPERNODE, 35 PK_BEFORE_STMT, 36 PK_AFTER_SUPERNODE, 37 38 /* Special values used for hash_map: */ 39 PK_EMPTY, 40 PK_DELETED, 41 42 NUM_POINT_KINDS 43 }; 44 45 extern const char *point_kind_to_string (enum point_kind pk); 46 47 class format 48 { 49 public: format(bool newlines)50 format (bool newlines) : m_newlines (newlines) {} 51 spacer(pretty_printer * pp)52 void spacer (pretty_printer *pp) const 53 { 54 if (m_newlines) 55 pp_newline (pp); 56 else 57 pp_space (pp); 58 } 59 60 bool m_newlines; 61 }; 62 63 /* A class for representing a location within the program, without 64 interprocedural information. 65 66 This represents a fine-grained location within the supergraph (or 67 within one of its nodes). */ 68 69 class function_point 70 { 71 public: function_point(const supernode * supernode,const superedge * from_edge,unsigned stmt_idx,enum point_kind kind)72 function_point (const supernode *supernode, 73 const superedge *from_edge, 74 unsigned stmt_idx, 75 enum point_kind kind) 76 : m_supernode (supernode), m_from_edge (from_edge), 77 m_stmt_idx (stmt_idx), m_kind (kind) 78 { 79 if (from_edge) 80 { 81 gcc_checking_assert (m_kind == PK_BEFORE_SUPERNODE); 82 gcc_checking_assert (from_edge->get_kind () == SUPEREDGE_CFG_EDGE); 83 } 84 if (stmt_idx) 85 gcc_checking_assert (m_kind == PK_BEFORE_STMT); 86 } 87 88 void print (pretty_printer *pp, const format &f) const; 89 void print_source_line (pretty_printer *pp) const; 90 void dump () const; 91 92 hashval_t hash () const; 93 bool operator== (const function_point &other) const 94 { 95 return (m_supernode == other.m_supernode 96 && m_from_edge == other.m_from_edge 97 && m_stmt_idx == other.m_stmt_idx 98 && m_kind == other.m_kind); 99 } 100 101 /* Accessors. */ 102 get_supernode()103 const supernode *get_supernode () const { return m_supernode; } get_function()104 function *get_function () const 105 { 106 if (m_supernode) 107 return m_supernode->m_fun; 108 else 109 return NULL; 110 } 111 const gimple *get_stmt () const; 112 location_t get_location () const; get_kind()113 enum point_kind get_kind () const { return m_kind; } get_from_edge()114 const superedge *get_from_edge () const 115 { 116 return m_from_edge; 117 } get_stmt_idx()118 unsigned get_stmt_idx () const 119 { 120 gcc_assert (m_kind == PK_BEFORE_STMT); 121 return m_stmt_idx; 122 } 123 124 /* Factory functions for making various kinds of program_point. */ 125 from_function_entry(const supergraph & sg,function * fun)126 static function_point from_function_entry (const supergraph &sg, 127 function *fun) 128 { 129 return before_supernode (sg.get_node_for_function_entry (fun), 130 NULL); 131 } 132 before_supernode(const supernode * supernode,const superedge * from_edge)133 static function_point before_supernode (const supernode *supernode, 134 const superedge *from_edge) 135 { 136 if (from_edge && from_edge->get_kind () != SUPEREDGE_CFG_EDGE) 137 from_edge = NULL; 138 return function_point (supernode, from_edge, 0, PK_BEFORE_SUPERNODE); 139 } 140 before_stmt(const supernode * supernode,unsigned stmt_idx)141 static function_point before_stmt (const supernode *supernode, 142 unsigned stmt_idx) 143 { 144 return function_point (supernode, NULL, stmt_idx, PK_BEFORE_STMT); 145 } 146 after_supernode(const supernode * supernode)147 static function_point after_supernode (const supernode *supernode) 148 { 149 return function_point (supernode, NULL, 0, PK_AFTER_SUPERNODE); 150 } 151 152 /* Support for hash_map. */ 153 empty()154 static function_point empty () 155 { 156 return function_point (NULL, NULL, 0, PK_EMPTY); 157 } deleted()158 static function_point deleted () 159 { 160 return function_point (NULL, NULL, 0, PK_DELETED); 161 } 162 163 static int cmp_within_supernode_1 (const function_point &point_a, 164 const function_point &point_b); 165 static int cmp_within_supernode (const function_point &point_a, 166 const function_point &point_b); 167 168 private: 169 const supernode *m_supernode; 170 171 /* For PK_BEFORE_SUPERNODE, and only for CFG edges. */ 172 const superedge *m_from_edge; 173 174 /* Only for PK_BEFORE_STMT. */ 175 unsigned m_stmt_idx; 176 177 enum point_kind m_kind; 178 }; 179 180 /* A class for representing a location within the program, including 181 interprocedural information. 182 183 This represents a fine-grained location within the supergraph (or 184 within one of its nodes), along with a call string giving the 185 interprocedural context. */ 186 187 class program_point 188 { 189 public: program_point(const function_point & fn_point,const call_string & call_string)190 program_point (const function_point &fn_point, 191 const call_string &call_string) 192 : m_function_point (fn_point), 193 m_call_string (call_string) 194 { 195 } 196 197 void print (pretty_printer *pp, const format &f) const; 198 void print_source_line (pretty_printer *pp) const; 199 void dump () const; 200 201 hashval_t hash () const; 202 bool operator== (const program_point &other) const 203 { 204 return (m_function_point == other.m_function_point 205 && m_call_string == other.m_call_string); 206 } 207 208 /* Accessors. */ 209 get_function_point()210 const function_point &get_function_point () const { return m_function_point; } get_call_string()211 const call_string &get_call_string () const { return m_call_string; } 212 get_supernode()213 const supernode *get_supernode () const 214 { 215 return m_function_point.get_supernode (); 216 } get_function()217 function *get_function () const 218 { 219 return m_function_point.get_function (); 220 } 221 function *get_function_at_depth (unsigned depth) const; get_fndecl()222 tree get_fndecl () const 223 { 224 gcc_assert (get_kind () != PK_ORIGIN); 225 return get_function ()->decl; 226 } get_stmt()227 const gimple *get_stmt () const 228 { 229 return m_function_point.get_stmt (); 230 } get_location()231 location_t get_location () const 232 { 233 return m_function_point.get_location (); 234 } get_kind()235 enum point_kind get_kind () const 236 { 237 return m_function_point.get_kind (); 238 } get_from_edge()239 const superedge *get_from_edge () const 240 { 241 return m_function_point.get_from_edge (); 242 } get_stmt_idx()243 unsigned get_stmt_idx () const 244 { 245 return m_function_point.get_stmt_idx (); 246 } 247 248 /* Get the number of frames we expect at this program point. 249 This will be one more than the length of the call_string 250 (which stores the parent callsites), apart from the origin 251 node, which doesn't have any frames. */ get_stack_depth()252 int get_stack_depth () const 253 { 254 if (get_kind () == PK_ORIGIN) 255 return 0; 256 return m_call_string.length () + 1; 257 } 258 259 /* Factory functions for making various kinds of program_point. */ 260 from_function_entry(const supergraph & sg,function * fun)261 static program_point from_function_entry (const supergraph &sg, 262 function *fun) 263 { 264 return program_point (function_point::from_function_entry (sg, fun), 265 call_string ()); 266 } 267 before_supernode(const supernode * supernode,const superedge * from_edge,const call_string & call_string)268 static program_point before_supernode (const supernode *supernode, 269 const superedge *from_edge, 270 const call_string &call_string) 271 { 272 return program_point (function_point::before_supernode (supernode, 273 from_edge), 274 call_string); 275 } 276 before_stmt(const supernode * supernode,unsigned stmt_idx,const call_string & call_string)277 static program_point before_stmt (const supernode *supernode, 278 unsigned stmt_idx, 279 const call_string &call_string) 280 { 281 return program_point (function_point::before_stmt (supernode, stmt_idx), 282 call_string); 283 } 284 after_supernode(const supernode * supernode,const call_string & call_string)285 static program_point after_supernode (const supernode *supernode, 286 const call_string &call_string) 287 { 288 return program_point (function_point::after_supernode (supernode), 289 call_string); 290 } 291 292 /* Support for hash_map. */ 293 empty()294 static program_point empty () 295 { 296 return program_point (function_point::empty (), call_string ()); 297 } deleted()298 static program_point deleted () 299 { 300 return program_point (function_point::deleted (), call_string ()); 301 } 302 303 bool on_edge (exploded_graph &eg, const superedge *succ); 304 305 void validate () const; 306 307 private: 308 const function_point m_function_point; 309 call_string m_call_string; 310 }; 311 312 } // namespace ana 313 314 #endif /* GCC_ANALYZER_PROGRAM_POINT_H */ 315