1 // Instruction-related RTL SSA classes -*- C++ -*- 2 // Copyright (C) 2020-2022 Free Software Foundation, Inc. 3 // 4 // This file is part of GCC. 5 // 6 // GCC is free software; you can redistribute it and/or modify it under 7 // the terms of the GNU General Public License as published by the Free 8 // Software Foundation; either version 3, or (at your option) any later 9 // version. 10 // 11 // GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12 // WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 // for more details. 15 // 16 // You should have received a copy of the GNU General Public License 17 // along with GCC; see the file COPYING3. If not see 18 // <http://www.gnu.org/licenses/>. 19 20 namespace rtl_ssa { 21 22 // A fake cost for instructions that we haven't costed yet. 23 const int UNKNOWN_COST = INT_MAX; 24 25 // Enumerates the kinds of note that can be added to an instruction. 26 // See the comment above insn_info for details. 27 enum class insn_note_kind : uint8_t 28 { 29 ORDER_NODE, 30 CALL_CLOBBERS 31 }; 32 33 // The base class for notes that can be added to an instruction. 34 // See the comment above insn_info for details. 35 class insn_note 36 { 37 // Size: 2 LP64 words. 38 friend class insn_info; 39 friend class function_info; 40 41 public: 42 // Return what kind of note this is. kind()43 insn_note_kind kind () const { return m_kind; } 44 45 // Return the next note in the list, or null if none. next_note()46 insn_note *next_note () const { return m_next_note; } 47 48 // Used with T = Derived *, where Derived is derived from insn_note. 49 // Convert the note to Derived, asserting that it has the right kind. 50 template<typename T> 51 T as_a (); 52 53 // Used with T = Derived *, where Derived is derived from insn_note. 54 // If the note is a Derived note, return it in that form, otherwise 55 // return null. 56 template<typename T> 57 T dyn_cast (); 58 59 protected: 60 // Construct a note with the given kind. 61 insn_note (insn_note_kind); 62 63 private: 64 // The next note in the list, or null if none. 65 insn_note *m_next_note; 66 67 // The kind of note this is. 68 insn_note_kind m_kind : 8; 69 70 protected: 71 // Fill in the remaining LP64 word with data that derived classes can use. 72 unsigned int m_data8 : 8; 73 unsigned int m_data16 : 16; 74 unsigned int m_data32 : 32; 75 }; 76 77 // Instructions have one of these notes if insn_info::has_call_clobbers () 78 // is true. All such instructions in an EBB are first grouped together 79 // by the predefined_function_abis of the functions that they call. 80 // Then, for each such predefined ABI, the call_clobbers notes are put 81 // into a splay tree whose nodes follow execution order. 82 class insn_call_clobbers_note : public insn_note 83 { 84 friend class function_info; 85 friend class default_splay_tree_accessors<insn_call_clobbers_note *>; 86 87 public: 88 static const insn_note_kind kind = insn_note_kind::CALL_CLOBBERS; 89 90 // Return the identifier of the predefined_function_abi. abi_id()91 unsigned int abi_id () const { return m_data32; } 92 93 // Return the instruction to which the note is attached. insn()94 insn_info *insn () const { return m_insn; } 95 96 protected: 97 insn_call_clobbers_note (unsigned int abi_id, insn_info *insn); 98 99 // The splay tree pointers. 100 insn_call_clobbers_note *m_children[2]; 101 102 // The value returned by insn (). 103 insn_info *m_insn; 104 }; 105 106 // A splay tree of insn_call_clobbers_notes. 107 using insn_call_clobbers_tree = default_splay_tree<insn_call_clobbers_note *>; 108 109 // SSA-related information about an instruction. It also represents 110 // artificial instructions that are added to make the dataflow correct; 111 // these artificial instructions fall into three categories: 112 // 113 // - Instructions that hold the phi nodes for an extended basic block (is_phi). 114 // 115 // - Instructions that represent the head of a basic block and that hold 116 // all the associated artificial uses and definitions. 117 // 118 // - Instructions that represent the end of a basic block and that again 119 // hold all the associated artificial uses and definitions. 120 // 121 // Dataflow-wise, each instruction goes through three stages: 122 // 123 // (1) Use all the values in uses (). 124 // 125 // (2) If has_call_clobbers (), clobber the registers indicated by 126 // insn_callee_abi. 127 // 128 // (3) Define all the values in defs (). 129 // 130 // Having stage (2) is a trade-off: it makes processing the instructions 131 // more complicated, but it saves having to allocate memory for every 132 // individual call clobber. Without it, clobbers for calls would often 133 // make up a large proportion of the total definitions in a function. 134 // 135 // All the instructions in a function are chained together in a list 136 // that follows a reverse postorder traversal of the CFG. The list 137 // contains both debug and nondebug instructions, but it is possible 138 // to hop from one nondebug instruction to the next with constant complexity. 139 // 140 // Instructions can have supplemental information attached in the form 141 // of "notes", a bit like REG_NOTES for the underlying RTL insns. 142 class insn_info 143 { 144 // Size: 9 LP64 words. 145 friend class ebb_info; 146 friend class function_info; 147 148 public: 149 // Compare instructions by their positions in the function list described 150 // above. Thus for two instructions in the same basic block, I1 < I2 if 151 // I1 comes before I2 in the block. 152 bool operator< (const insn_info &) const; 153 bool operator<= (const insn_info &) const; 154 bool operator>= (const insn_info &) const; 155 bool operator> (const insn_info &) const; 156 157 // Return -1 if this instruction comes before INSN in the reverse 158 // postorder, 0 if this instruction is INSN, or 1 if this instruction 159 // comes after INSN in the reverse postorder. 160 int compare_with (const insn_info *insn) const; 161 162 // Return the previous and next instructions in the list described above, 163 // or null if there are no such instructions. 164 insn_info *prev_any_insn () const; 165 insn_info *next_any_insn () const; 166 167 // Only valid if !is_debug_insn (). Return the previous and next 168 // nondebug instructions in the list described above, skipping over 169 // any intervening debug instructions. These are constant-time operations. 170 insn_info *prev_nondebug_insn () const; 171 insn_info *next_nondebug_insn () const; 172 173 // Return the underlying RTL insn. This instruction is null if is_phi () 174 // or is_bb_end () are true. The instruction is a basic block note if 175 // is_bb_head () is true. rtl()176 rtx_insn *rtl () const { return m_rtl; } 177 178 // Return true if the instruction is a real insn with an rtl pattern. 179 // Return false if it is an artificial instruction that represents the 180 // phi nodes in an extended basic block or the head or end of a basic block. is_real()181 bool is_real () const { return m_cost_or_uid >= 0; } 182 183 // Return the opposite of is_real (). is_artificial()184 bool is_artificial () const { return m_cost_or_uid < 0; } 185 186 // Return true if the instruction was a real instruction but has now 187 // been deleted. In this case the instruction is no longer part of 188 // the SSA information. has_been_deleted()189 bool has_been_deleted () const { return m_rtl && !INSN_P (m_rtl); } 190 191 // Return true if the instruction is a debug instruction (and thus 192 // also a real instruction). is_debug_insn()193 bool is_debug_insn () const { return m_is_debug_insn; } 194 195 // Return true if the instruction is something that we can optimize. 196 // This implies that it is a real instruction that contains an asm 197 // or that contains something that matches an .md define_insn pattern. can_be_optimized()198 bool can_be_optimized () const { return m_can_be_optimized; } 199 200 // Return true if the instruction is a call instruction. 201 // 202 // ??? We could cache this information, but since most callers would 203 // go on to access PATTERN (rtl ()), a cache might not be helpful and 204 // could even be counterproductive. is_call()205 bool is_call () const { return CALL_P (m_rtl); } 206 207 // Return true if the instruction is a jump instruction. 208 // 209 // ??? See is_call for the reason we don't cache this. is_jump()210 bool is_jump () const { return JUMP_P (m_rtl); } 211 212 // Return true if the instruction is real and contains an inline asm. is_asm()213 bool is_asm () const { return m_is_asm; } 214 215 // Return true if the instruction is real and includes an RTX_AUTOINC 216 // operation. has_pre_post_modify()217 bool has_pre_post_modify () const { return m_has_pre_post_modify; } 218 219 // Return true if the instruction is real and has volatile references, 220 // in the sense of volatile_refs_p. This includes volatile memory, 221 // volatile asms and UNSPEC_VOLATILEs. has_volatile_refs()222 bool has_volatile_refs () const { return m_has_volatile_refs; } 223 224 // Return true if the instruction is aritificial and if its (sole) 225 // purpose is to hold the phi nodes in an extended basic block. 226 bool is_phi () const; 227 228 // Return true if the instruction is artificial and if it represents 229 // the head of a basic block. If so, the instruction conceptually 230 // executes before the real instructions in the block. The uses 231 // and definitions represent the df_get_artificial_uses and 232 // df_get_artificial_defs entries for the head of the block. 233 bool is_bb_head () const; 234 235 // Return true if the instruction is artificial and if it represents 236 // the end of a basic block. The uses and definitions represent the 237 // the df_get_artificial_uses and df_get_artificial_defs entries for 238 // the end of the block. 239 bool is_bb_end () const; 240 241 // Return the basic block that the instruction is in. bb()242 bb_info *bb () const { return m_bb; } 243 244 // Return the extended basic block that the instruction is in; 245 // see bb_info for details. 246 ebb_info *ebb () const; 247 248 // If the instruction is real, return the unique identifier of the 249 // underlying RTL insn. If the instruction is artificial, return 250 // a unique negative identifier for the instructions. 251 // 252 // Note that the identifiers are not linear: it can be the case that 253 // an instruction with a higher uid comes earlier in a block than an 254 // instruction with a lower uid. The identifiers are however persistent; 255 // the identifier remains the same after the instruction has been moved 256 // or changed. 257 int uid () const; 258 259 // Return the list of things that this instruction uses. Registers 260 // come first, in register number order, followed by memory. 261 use_array uses () const; 262 263 // Return true if the instruction is a call and if the clobbers 264 // described by insn_callee_abi have been omitted from the list 265 // of definitions. 266 bool has_call_clobbers () const; 267 268 // Return the list of things that this instruction sets or clobbers. 269 // Registers come first, in register number order, followed by memory. 270 // 271 // If has_call_clobbers () is true, the list omits both the full and 272 // partial register clobbers described by insn_callee_abi. 273 def_array defs () const; 274 275 // The number of entries in uses (). num_uses()276 unsigned int num_uses () const { return m_num_uses; } 277 278 // The number of entries in defs (). num_defs()279 unsigned int num_defs () const { return m_num_defs; } 280 281 // Return the cost of the instruction, as calculated by the target. 282 // For performance reasons, the cost is evaluated lazily on first use. 283 // 284 // Artificial instructions have a cost of 0. 285 unsigned int cost () const; 286 287 // Return the first insn_note attached to the instruction, or null 288 // if none. first_note()289 insn_note *first_note () const { return m_first_note; } 290 291 // See if a note of type T is attached to the instruction. Return it 292 // if so, otherwise return null. 293 template<typename T> 294 const T *find_note () const; 295 296 // Print "i" + uid () for real instructions and "a" + -uid () for 297 // artificial instructions. 298 void print_identifier (pretty_printer *) const; 299 300 // Print a short(ish) description of where the instruction is. 301 void print_location (pretty_printer *) const; 302 303 // Combine print_identifier and print_location. 304 void print_identifier_and_location (pretty_printer *) const; 305 306 // Print a full description of the instruction. 307 void print_full (pretty_printer *) const; 308 309 private: 310 // The first-order way of representing the order between instructions 311 // is to assign "program points", with higher point numbers coming 312 // later in the reverse postorder than lower point numbers. However, 313 // after a sequence of instruction movements, we may end up in a situation 314 // that adjacent instructions have the same program point. 315 // 316 // When that happens, we put the instructions into a splay tree that 317 // records their relative order. Each node of the splay tree is an 318 // order_node note that is attached to its respective instruction. 319 // The root of the splay tree is not stored, since the only thing 320 // we need the tree for is to compare two nodes. 321 class order_node : public insn_note 322 { 323 public: 324 static const insn_note_kind kind = insn_note_kind::ORDER_NODE; 325 326 order_node (int uid); 327 328 // Return the uid of the instruction that this node describes. uid()329 int uid () const { return m_data32; } 330 331 // The splay tree pointers. 332 order_node *m_children[2]; 333 order_node *m_parent; 334 }; 335 using order_splay_tree = default_rootless_splay_tree<order_node *>; 336 337 // prev_insn_or_last_debug_insn represents a choice between two things: 338 // 339 // (1) A pointer to the previous instruction in the list that has the 340 // same is_debug_insn () value, or null if no such instruction exists. 341 // 342 // (2) A pointer to the end of a sublist of debug instructions. 343 // 344 // (2) is used if this instruction is a debug instruction and the 345 // previous instruction is not. (1) is used otherwise. 346 // 347 // next_nondebug_or_debug_insn points to the next instruction but also 348 // records whether that next instruction is a debug instruction or a 349 // nondebug instruction. 350 // 351 // Thus the list is chained as follows: 352 // 353 // ----> ----> ----> ----> ----> 354 // NONDEBUG NONDEBUG DEBUG DEBUG DEBUG NONDEBUG ... 355 // <---- ^ +-- <---- <---- ^ +-- 356 // | | | | 357 // | +------------------------+ | 358 // | | 359 // +-----------------------------------+ 360 using prev_insn_or_last_debug_insn = pointer_mux<insn_info>; 361 using next_nondebug_or_debug_insn = pointer_mux<insn_info>; 362 363 insn_info (bb_info *bb, rtx_insn *rtl, int cost_or_uid); 364 365 static void print_uid (pretty_printer *, int); 366 367 void calculate_cost () const; 368 void set_properties (const rtx_properties &); 369 void set_accesses (access_info **, unsigned int, unsigned int); 370 void copy_accesses (access_array, access_array); set_cost(unsigned int cost)371 void set_cost (unsigned int cost) { m_cost_or_uid = cost; } set_bb(bb_info * bb)372 void set_bb (bb_info *bb) { m_bb = bb; } 373 374 void add_note (insn_note *note); 375 376 order_node *get_order_node () const; 377 order_node *get_known_order_node () const; 378 int slow_compare_with (const insn_info &) const; 379 380 insn_info *last_debug_insn () const; 381 point()382 unsigned int point () const { return m_point; } 383 void copy_prev_from (insn_info *); 384 void copy_next_from (insn_info *); 385 void set_prev_sametype_insn (insn_info *); 386 void set_last_debug_insn (insn_info *); 387 void set_next_any_insn (insn_info *); set_point(unsigned int point)388 void set_point (unsigned int point) { m_point = point; } 389 void clear_insn_links (); 390 bool has_insn_links (); 391 392 // The values returned by the accessors above. 393 prev_insn_or_last_debug_insn m_prev_insn_or_last_debug_insn; 394 next_nondebug_or_debug_insn m_next_nondebug_or_debug_insn; 395 bb_info *m_bb; 396 rtx_insn *m_rtl; 397 398 // The list of definitions followed by the list of uses. 399 access_info **m_accesses; 400 401 // The number of definitions and the number uses. FIRST_PSEUDO_REGISTER + 1 402 // is the maximum number of accesses to hard registers and memory, and 403 // MAX_RECOG_OPERANDS is the maximum number of pseudos that can be 404 // defined by an instruction, so the number of definitions in a real 405 // instruction should fit easily in 16 bits. However, there are no 406 // limits on the number of definitions in artifical instructions. 407 unsigned int m_num_uses; 408 unsigned int m_num_defs; 409 410 // Flags returned by the accessors above. 411 unsigned int m_is_debug_insn : 1; 412 unsigned int m_can_be_optimized : 1; 413 unsigned int m_is_asm : 1; 414 unsigned int m_has_pre_post_modify : 1; 415 unsigned int m_has_volatile_refs : 1; 416 417 // For future expansion. 418 unsigned int m_spare : 27; 419 420 // The program point at which the instruction occurs. 421 // 422 // Note that the values of the program points are influenced by -g 423 // and so should not used to make codegen decisions. 424 unsigned int m_point; 425 426 // Negative if the instruction is artificial, nonnegative if it is real. 427 // 428 // For real instructions: the cost of the instruction, or UNKNOWN_COST 429 // if we haven't measured it yet. 430 // 431 // For artificial instructions: the (negative) unique identifier of the 432 // instruction. 433 mutable int m_cost_or_uid; 434 435 // On LP64 systems, there's a gap here that could be used for future 436 // expansion. 437 438 // The list of notes that have been attached to the instruction. 439 insn_note *m_first_note; 440 }; 441 442 // Iterators for unfiltered lists of instructions. 443 using any_insn_iterator = list_iterator<insn_info, &insn_info::next_any_insn>; 444 using reverse_any_insn_iterator 445 = list_iterator<insn_info, &insn_info::prev_any_insn>; 446 447 // Iterators for nondebug instructions only. 448 using nondebug_insn_iterator 449 = list_iterator<insn_info, &insn_info::next_nondebug_insn>; 450 using reverse_nondebug_insn_iterator 451 = list_iterator<insn_info, &insn_info::prev_nondebug_insn>; 452 453 // A class that describes an inclusive range of instructions. 454 class insn_range_info 455 { 456 public: 457 insn_range_info () = default; 458 459 // Create a range that contains a singleton instruction. insn_range_info(insn_info * insn)460 insn_range_info (insn_info *insn) : first (insn), last (insn) {} 461 462 // Create a range [FIRST, LAST], given that *FIRST <= *LAST. 463 insn_range_info (insn_info *first, insn_info *last); 464 465 // Return true if the range contains at least one instruction. 466 explicit operator bool () const { return *first <= *last; } 467 468 bool operator== (const insn_range_info &) const; 469 bool operator!= (const insn_range_info &) const; 470 471 // If the range contains a single instruction, return that instruction, 472 // otherwise return null. 473 insn_info *singleton () const; 474 475 // Return true if the range includes INSN. 476 bool includes (insn_info *insn) const; 477 478 // If INSN is inside the range, return INSN, otherwise return the 479 // nearest in-range instruction. 480 insn_info *clamp_insn_to_range (insn_info *insn) const; 481 482 // Return true if this range is a subrange of OTHER, i.e. if OTHER 483 // includes every instruction that this range does. 484 bool is_subrange_of (const insn_range_info &other) const; 485 486 // The lower and upper bounds of the range. 487 insn_info *first; 488 insn_info *last; 489 }; 490 491 // A class that represents a closure of operator== for instructions. 492 // This is used by insn_is; see there for details. 493 class insn_is_closure 494 { 495 public: insn_is_closure(const insn_info * insn)496 insn_is_closure (const insn_info *insn) : m_insn (insn) {} operator()497 bool operator() (const insn_info *other) const { return m_insn == other; } 498 499 private: 500 const insn_info *m_insn; 501 }; 502 503 void pp_insn (pretty_printer *, const insn_info *); 504 505 } 506 507 void dump (FILE *, const rtl_ssa::insn_info *); 508 509 void DEBUG_FUNCTION debug (const rtl_ssa::insn_info *); 510