1 /* Context-aware pointer equivalence tracker. 2 Copyright (C) 2020-2022 Free Software Foundation, Inc. 3 Contributed by Aldy Hernandez <aldyh@redhat.com> 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it under 8 the terms of the GNU General Public License as published by the Free 9 Software Foundation; either version 3, or (at your option) any later 10 version. 11 12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13 WARRANTY; without even the implied warranty of MERCHANTABILITY or 14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15 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 "backend.h" 25 #include "tree.h" 26 #include "gimple.h" 27 #include "tree-pass.h" 28 #include "ssa.h" 29 #include "gimple-pretty-print.h" 30 #include "cfganal.h" 31 #include "gimple-fold.h" 32 #include "tree-eh.h" 33 #include "gimple-iterator.h" 34 #include "tree-cfg.h" 35 #include "tree-ssa-loop-manip.h" 36 #include "tree-ssa-loop.h" 37 #include "cfgloop.h" 38 #include "tree-scalar-evolution.h" 39 #include "tree-ssa-propagate.h" 40 #include "alloc-pool.h" 41 #include "domwalk.h" 42 #include "tree-cfgcleanup.h" 43 #include "vr-values.h" 44 #include "gimple-range.h" 45 #include "fold-const.h" 46 #include "value-pointer-equiv.h" 47 48 // Unwindable SSA equivalence table for pointers. 49 // 50 // The main query point is get_replacement() which returns what a 51 // given SSA can be replaced with in the current scope. 52 53 class ssa_equiv_stack 54 { 55 public: 56 ssa_equiv_stack (); 57 void enter (basic_block); 58 void leave (basic_block); 59 void push_replacement (tree name, tree replacement); 60 tree get_replacement (tree name); 61 62 private: 63 auto_vec<std::pair <tree, tree>> m_stack; 64 auto_vec<tree> m_replacements; 65 const std::pair <tree, tree> m_marker = std::make_pair (NULL, NULL); 66 }; 67 68 ssa_equiv_stack::ssa_equiv_stack () 69 { 70 m_replacements.safe_grow_cleared (num_ssa_names + 1); 71 } 72 73 // Pushes a marker at the given point. 74 75 void 76 ssa_equiv_stack::enter (basic_block) 77 { 78 m_stack.safe_push (m_marker); 79 } 80 81 // Pops the stack to the last marker, while performing replacements 82 // along the way. 83 84 void 85 ssa_equiv_stack::leave (basic_block) 86 { 87 gcc_checking_assert (!m_stack.is_empty ()); 88 while (m_stack.last () != m_marker) 89 { 90 std::pair<tree, tree> e = m_stack.pop (); 91 m_replacements[SSA_NAME_VERSION (e.first)] = e.second; 92 } 93 m_stack.pop (); 94 } 95 96 // Set the equivalence of NAME to REPLACEMENT. 97 98 void 99 ssa_equiv_stack::push_replacement (tree name, tree replacement) 100 { 101 unsigned v = SSA_NAME_VERSION (name); 102 103 if (v >= m_replacements.length ()) 104 m_replacements.safe_grow_cleared (num_ssa_names + 1); 105 106 tree old = m_replacements[v]; 107 m_replacements[v] = replacement; 108 m_stack.safe_push (std::make_pair (name, old)); 109 } 110 111 // Return the equivalence of NAME. 112 113 tree 114 ssa_equiv_stack::get_replacement (tree name) 115 { 116 unsigned v = SSA_NAME_VERSION (name); 117 118 if (v >= m_replacements.length ()) 119 m_replacements.safe_grow_cleared (num_ssa_names + 1); 120 121 return m_replacements[v]; 122 } 123 124 pointer_equiv_analyzer::pointer_equiv_analyzer (gimple_ranger *r) 125 { 126 m_ranger = r; 127 m_global_points.safe_grow_cleared (num_ssa_names + 1); 128 m_cond_points = new ssa_equiv_stack; 129 } 130 131 pointer_equiv_analyzer::~pointer_equiv_analyzer () 132 { 133 delete m_cond_points; 134 } 135 136 // Set the global pointer equivalency for SSA to POINTEE. 137 138 void 139 pointer_equiv_analyzer::set_global_equiv (tree ssa, tree pointee) 140 { 141 unsigned v = SSA_NAME_VERSION (ssa); 142 143 if (v >= m_global_points.length ()) 144 m_global_points.safe_grow_cleared (num_ssa_names + 1); 145 146 m_global_points[v] = pointee; 147 } 148 149 // Set the conditional pointer equivalency for SSA to POINTEE. 150 151 void 152 pointer_equiv_analyzer::set_cond_equiv (tree ssa, tree pointee) 153 { 154 m_cond_points->push_replacement (ssa, pointee); 155 } 156 157 // Return the current pointer equivalency info for SSA, or NULL if 158 // none is available. Note that global info takes priority over 159 // conditional info. 160 161 tree 162 pointer_equiv_analyzer::get_equiv (tree ssa) 163 { 164 unsigned v = SSA_NAME_VERSION (ssa); 165 166 if (v >= m_global_points.length ()) 167 m_global_points.safe_grow_cleared (num_ssa_names + 1); 168 169 tree ret = m_global_points[v]; 170 if (ret) 171 return ret; 172 return m_cond_points->get_replacement (ssa); 173 } 174 175 // Method to be called on entry to a BB. 176 177 void 178 pointer_equiv_analyzer::enter (basic_block bb) 179 { 180 m_cond_points->enter (bb); 181 182 for (gphi_iterator iter = gsi_start_phis (bb); 183 !gsi_end_p (iter); 184 gsi_next (&iter)) 185 { 186 gphi *phi = iter.phi (); 187 tree lhs = gimple_phi_result (phi); 188 if (!POINTER_TYPE_P (TREE_TYPE (lhs))) 189 continue; 190 tree arg0 = gimple_phi_arg_def (phi, 0); 191 if (TREE_CODE (arg0) == SSA_NAME && !is_gimple_min_invariant (arg0)) 192 arg0 = get_equiv (arg0); 193 if (arg0 && is_gimple_min_invariant (arg0)) 194 { 195 // If all the PHI args point to the same place, set the 196 // pointer equivalency info for the PHI result. This can 197 // happen for passes that create redundant PHIs like 198 // PHI<&foo, &foo> or PHI<&foo>. 199 for (size_t i = 1; i < gimple_phi_num_args (phi); ++i) 200 { 201 tree argi = gimple_phi_arg_def (phi, i); 202 if (TREE_CODE (argi) == SSA_NAME 203 && !is_gimple_min_invariant (argi)) 204 argi = get_equiv (argi); 205 if (!argi || !operand_equal_p (arg0, argi)) 206 return; 207 } 208 set_global_equiv (lhs, arg0); 209 } 210 } 211 212 edge pred = single_pred_edge_ignoring_loop_edges (bb, false); 213 if (pred) 214 visit_edge (pred); 215 } 216 217 // Method to be called on exit from a BB. 218 219 void 220 pointer_equiv_analyzer::leave (basic_block bb) 221 { 222 m_cond_points->leave (bb); 223 } 224 225 // Helper function to return the pointer equivalency information for 226 // EXPR from a gimple statement with CODE. This returns either the 227 // cached pointer equivalency info for an SSA, or an invariant in case 228 // EXPR is one (i.e. &foo). Returns NULL if EXPR is neither an SSA 229 // nor an invariant. 230 231 tree 232 pointer_equiv_analyzer::get_equiv_expr (tree_code code, tree expr) 233 { 234 if (code == SSA_NAME) 235 return get_equiv (expr); 236 237 if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS 238 && is_gimple_min_invariant (expr)) 239 return expr; 240 241 return NULL; 242 } 243 244 // Hack to provide context to the gimple fold callback. 245 static struct 246 { 247 gimple *m_stmt; 248 gimple_ranger *m_ranger; 249 pointer_equiv_analyzer *m_pta; 250 } x_fold_context; 251 252 // Gimple fold callback. 253 static tree 254 pta_valueize (tree name) 255 { 256 tree ret 257 = x_fold_context.m_ranger->value_of_expr (name, x_fold_context.m_stmt); 258 259 if (!ret && supported_pointer_equiv_p (name)) 260 ret = x_fold_context.m_pta->get_equiv (name); 261 262 return ret ? ret : name; 263 } 264 265 // Method to be called on gimple statements during traversal of the IL. 266 267 void 268 pointer_equiv_analyzer::visit_stmt (gimple *stmt) 269 { 270 if (gimple_code (stmt) != GIMPLE_ASSIGN) 271 return; 272 273 tree lhs = gimple_assign_lhs (stmt); 274 if (!supported_pointer_equiv_p (lhs)) 275 return; 276 277 tree rhs = gimple_assign_rhs1 (stmt); 278 rhs = get_equiv_expr (gimple_assign_rhs_code (stmt), rhs); 279 if (rhs) 280 { 281 set_global_equiv (lhs, rhs); 282 return; 283 } 284 285 // If we couldn't find anything, try fold. 286 x_fold_context = { stmt, m_ranger, this}; 287 rhs = gimple_fold_stmt_to_constant_1 (stmt, pta_valueize, pta_valueize); 288 if (rhs) 289 { 290 rhs = get_equiv_expr (TREE_CODE (rhs), rhs); 291 if (rhs) 292 { 293 set_global_equiv (lhs, rhs); 294 return; 295 } 296 } 297 } 298 299 // If the edge in E is a conditional that sets a pointer equality, set the 300 // conditional pointer equivalency information. 301 302 void 303 pointer_equiv_analyzer::visit_edge (edge e) 304 { 305 gimple *stmt = last_stmt (e->src); 306 tree lhs; 307 // Recognize: x_13 [==,!=] &foo. 308 if (stmt 309 && gimple_code (stmt) == GIMPLE_COND 310 && (lhs = gimple_cond_lhs (stmt)) 311 && TREE_CODE (lhs) == SSA_NAME 312 && POINTER_TYPE_P (TREE_TYPE (lhs)) 313 && TREE_CODE (gimple_cond_rhs (stmt)) == ADDR_EXPR) 314 { 315 tree_code code = gimple_cond_code (stmt); 316 if ((code == EQ_EXPR && e->flags & EDGE_TRUE_VALUE) 317 || ((code == NE_EXPR && e->flags & EDGE_FALSE_VALUE))) 318 set_cond_equiv (lhs, gimple_cond_rhs (stmt)); 319 } 320 } 321