1 /* Communication between registering jump thread requests and 2 updating the SSA/CFG for jump threading. 3 Copyright (C) 2013-2021 Free Software Foundation, Inc. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify 8 it 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, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU 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 _TREE_SSA_THREADUPDATE_H 22 #define _TREE_SSA_THREADUPDATE_H 1 23 24 enum jump_thread_edge_type 25 { 26 EDGE_START_JUMP_THREAD, 27 EDGE_COPY_SRC_BLOCK, 28 EDGE_COPY_SRC_JOINER_BLOCK, 29 EDGE_NO_COPY_SRC_BLOCK 30 }; 31 32 // We keep the registered jump threading opportunities in this 33 // vector as edge pairs (original_edge, target_edge). 34 35 class jump_thread_edge 36 { 37 public: jump_thread_edge(edge e,jump_thread_edge_type t)38 jump_thread_edge (edge e, jump_thread_edge_type t) : e (e), type (t) {} 39 40 edge e; 41 jump_thread_edge_type type; 42 }; 43 44 class jump_thread_path_allocator 45 { 46 public: 47 jump_thread_path_allocator (); 48 ~jump_thread_path_allocator (); 49 jump_thread_edge *allocate_thread_edge (edge, jump_thread_edge_type); 50 vec<jump_thread_edge *> *allocate_thread_path (); 51 private: 52 DISABLE_COPY_AND_ASSIGN (jump_thread_path_allocator); 53 obstack m_obstack; 54 }; 55 56 // Abstract class for the jump thread registry. 57 // 58 // When all candidates have been registered with 59 // register_jump_thread(), thread_through_all_blocks() is called to 60 // update the CFG. 61 62 class jt_path_registry 63 { 64 public: 65 jt_path_registry (bool backedge_threads); 66 virtual ~jt_path_registry (); 67 bool register_jump_thread (vec<jump_thread_edge *> *); 68 bool thread_through_all_blocks (bool peel_loop_headers); 69 void push_edge (vec<jump_thread_edge *> *path, edge, jump_thread_edge_type); 70 vec<jump_thread_edge *> *allocate_thread_path (); 71 void debug (); 72 protected: 73 void debug_path (FILE *, int pathno); 74 vec<vec<jump_thread_edge *> *> m_paths; 75 unsigned long m_num_threaded_edges; 76 private: 77 virtual bool update_cfg (bool peel_loop_headers) = 0; 78 bool cancel_invalid_paths (vec<jump_thread_edge *> &path); 79 jump_thread_path_allocator m_allocator; 80 // True if threading through back edges is allowed. This is only 81 // allowed in the generic copier in the backward threader. 82 bool m_backedge_threads; 83 DISABLE_COPY_AND_ASSIGN (jt_path_registry); 84 }; 85 86 // Forward threader path registry using a custom BB copier. 87 88 class fwd_jt_path_registry : public jt_path_registry 89 { 90 public: 91 fwd_jt_path_registry (); 92 ~fwd_jt_path_registry (); 93 void remove_jump_threads_including (edge); 94 private: 95 bool update_cfg (bool peel_loop_headers) override; 96 void mark_threaded_blocks (bitmap threaded_blocks); 97 bool thread_block_1 (basic_block, bool noloop_only, bool joiners); 98 bool thread_block (basic_block, bool noloop_only); 99 bool thread_through_loop_header (class loop *loop, 100 bool may_peel_loop_headers); 101 class redirection_data *lookup_redirection_data (edge e, enum insert_option); 102 103 hash_table<struct removed_edges> *m_removed_edges; 104 105 // Main data structure to hold information for duplicates of BB. 106 hash_table<redirection_data> *m_redirection_data; 107 }; 108 109 // Backward threader path registry using a generic BB copier. 110 111 class back_jt_path_registry : public jt_path_registry 112 { 113 public: 114 back_jt_path_registry (); 115 private: 116 bool update_cfg (bool peel_loop_headers) override; 117 void adjust_paths_after_duplication (unsigned curr_path_num); 118 bool duplicate_thread_path (edge entry, edge exit, basic_block *region, 119 unsigned n_region, unsigned current_path_no); 120 bool rewire_first_differing_edge (unsigned path_num, unsigned edge_num); 121 }; 122 123 // Rather than search all the edges in jump thread paths each time DOM 124 // is able to simply if control statement, we build a hash table with 125 // the deleted edges. We only care about the address of the edge, not 126 // its contents. 127 struct removed_edges : nofree_ptr_hash<edge_def> 128 { hashremoved_edges129 static hashval_t hash (edge e) { return htab_hash_pointer (e); } equalremoved_edges130 static bool equal (edge e1, edge e2) { return e1 == e2; } 131 }; 132 133 extern unsigned int estimate_threading_killed_stmts (basic_block); 134 135 enum bb_dom_status 136 { 137 /* BB does not dominate latch of the LOOP. */ 138 DOMST_NONDOMINATING, 139 /* The LOOP is broken (there is no path from the header to its latch. */ 140 DOMST_LOOP_BROKEN, 141 /* BB dominates the latch of the LOOP. */ 142 DOMST_DOMINATING 143 }; 144 145 enum bb_dom_status determine_bb_domination_status (class loop *, basic_block); 146 147 // In tree-ssa-dom.c. 148 extern void free_dom_edge_info (edge); 149 150 #endif 151