1/* Functions to analyze and validate GIMPLE trees. 2 Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3 Contributed by Diego Novillo <dnovillo@redhat.com> 4 Rewritten by Jason Merrill <jason@redhat.com> 5 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify 9it under the terms of the GNU General Public License as published by 10the Free Software Foundation; either version 2, or (at your option) 11any later version. 12 13GCC is distributed in the hope that it will be useful, 14but WITHOUT ANY WARRANTY; without even the implied warranty of 15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16GNU General Public License for more details. 17 18You should have received a copy of the GNU General Public License 19along with GCC; see the file COPYING. If not, write to 20the Free Software Foundation, 51 Franklin Street, Fifth Floor, 21Boston, MA 02110-1301, USA. */ 22 23#include "config.h" 24#include "system.h" 25#include "coretypes.h" 26#include "ggc.h" 27#include "tm.h" 28#include "tree.h" 29#include "tree-gimple.h" 30#include "tree-flow.h" 31#include "output.h" 32#include "rtl.h" 33#include "expr.h" 34#include "bitmap.h" 35 36/* For the definitive definition of GIMPLE, see doc/tree-ssa.texi. */ 37 38/* Validation of GIMPLE expressions. */ 39 40/* Return true if T is a GIMPLE RHS for an assignment to a temporary. */ 41 42bool 43is_gimple_formal_tmp_rhs (tree t) 44{ 45 enum tree_code code = TREE_CODE (t); 46 47 switch (TREE_CODE_CLASS (code)) 48 { 49 case tcc_unary: 50 case tcc_binary: 51 case tcc_comparison: 52 return true; 53 54 default: 55 break; 56 } 57 58 switch (code) 59 { 60 case TRUTH_NOT_EXPR: 61 case TRUTH_AND_EXPR: 62 case TRUTH_OR_EXPR: 63 case TRUTH_XOR_EXPR: 64 case ADDR_EXPR: 65 case CALL_EXPR: 66 case CONSTRUCTOR: 67 case COMPLEX_EXPR: 68 case INTEGER_CST: 69 case REAL_CST: 70 case STRING_CST: 71 case COMPLEX_CST: 72 case VECTOR_CST: 73 case OBJ_TYPE_REF: 74 case ASSERT_EXPR: 75 return true; 76 77 default: 78 break; 79 } 80 81 return is_gimple_lvalue (t) || is_gimple_val (t); 82} 83 84/* Returns true iff T is a valid RHS for an assignment to a renamed 85 user -- or front-end generated artificial -- variable. */ 86 87bool 88is_gimple_reg_rhs (tree t) 89{ 90 /* If the RHS of the MODIFY_EXPR may throw or make a nonlocal goto 91 and the LHS is a user variable, then we need to introduce a formal 92 temporary. This way the optimizers can determine that the user 93 variable is only modified if evaluation of the RHS does not throw. 94 95 Don't force a temp of a non-renamable type; the copy could be 96 arbitrarily expensive. Instead we will generate a V_MAY_DEF for 97 the assignment. */ 98 99 if (is_gimple_reg_type (TREE_TYPE (t)) 100 && ((TREE_CODE (t) == CALL_EXPR && TREE_SIDE_EFFECTS (t)) 101 || tree_could_throw_p (t))) 102 return false; 103 104 return is_gimple_formal_tmp_rhs (t); 105} 106 107/* Returns true iff T is a valid RHS for an assignment to an un-renamed 108 LHS, or for a call argument. */ 109 110bool 111is_gimple_mem_rhs (tree t) 112{ 113 /* If we're dealing with a renamable type, either source or dest must be 114 a renamed variable. Also force a temporary if the type doesn't need 115 to be stored in memory, since it's cheap and prevents erroneous 116 tailcalls (PR 17526). */ 117 if (is_gimple_reg_type (TREE_TYPE (t)) 118 || (TYPE_MODE (TREE_TYPE (t)) != BLKmode 119 && (TREE_CODE (t) != CALL_EXPR 120 || ! aggregate_value_p (t, t)))) 121 return is_gimple_val (t); 122 else 123 return is_gimple_formal_tmp_rhs (t); 124} 125 126/* Returns the appropriate RHS predicate for this LHS. */ 127 128gimple_predicate 129rhs_predicate_for (tree lhs) 130{ 131 if (is_gimple_formal_tmp_var (lhs)) 132 return is_gimple_formal_tmp_rhs; 133 else if (is_gimple_reg (lhs)) 134 return is_gimple_reg_rhs; 135 else 136 return is_gimple_mem_rhs; 137} 138 139/* Return true if T is a valid LHS for a GIMPLE assignment expression. */ 140 141bool 142is_gimple_lvalue (tree t) 143{ 144 return (is_gimple_addressable (t) 145 || TREE_CODE (t) == WITH_SIZE_EXPR 146 /* These are complex lvalues, but don't have addresses, so they 147 go here. */ 148 || TREE_CODE (t) == BIT_FIELD_REF); 149} 150 151/* Return true if T is a GIMPLE condition. */ 152 153bool 154is_gimple_condexpr (tree t) 155{ 156 return (is_gimple_val (t) || COMPARISON_CLASS_P (t)); 157} 158 159/* Return true if T is something whose address can be taken. */ 160 161bool 162is_gimple_addressable (tree t) 163{ 164 return (is_gimple_id (t) || handled_component_p (t) 165 || INDIRECT_REF_P (t)); 166} 167 168/* Return true if T is function invariant. Or rather a restricted 169 form of function invariant. */ 170 171bool 172is_gimple_min_invariant (tree t) 173{ 174 switch (TREE_CODE (t)) 175 { 176 case ADDR_EXPR: 177 return TREE_INVARIANT (t); 178 179 case INTEGER_CST: 180 case REAL_CST: 181 case STRING_CST: 182 case COMPLEX_CST: 183 case VECTOR_CST: 184 return true; 185 186 default: 187 return false; 188 } 189} 190 191/* Return true if T looks like a valid GIMPLE statement. */ 192 193bool 194is_gimple_stmt (tree t) 195{ 196 enum tree_code code = TREE_CODE (t); 197 198 switch (code) 199 { 200 case NOP_EXPR: 201 /* The only valid NOP_EXPR is the empty statement. */ 202 return IS_EMPTY_STMT (t); 203 204 case BIND_EXPR: 205 case COND_EXPR: 206 /* These are only valid if they're void. */ 207 return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t)); 208 209 case SWITCH_EXPR: 210 case GOTO_EXPR: 211 case RETURN_EXPR: 212 case LABEL_EXPR: 213 case CASE_LABEL_EXPR: 214 case TRY_CATCH_EXPR: 215 case TRY_FINALLY_EXPR: 216 case EH_FILTER_EXPR: 217 case CATCH_EXPR: 218 case ASM_EXPR: 219 case RESX_EXPR: 220 case PHI_NODE: 221 case STATEMENT_LIST: 222 case OMP_PARALLEL: 223 case OMP_FOR: 224 case OMP_SECTIONS: 225 case OMP_SECTION: 226 case OMP_SINGLE: 227 case OMP_MASTER: 228 case OMP_ORDERED: 229 case OMP_CRITICAL: 230 case OMP_RETURN: 231 case OMP_CONTINUE: 232 /* These are always void. */ 233 return true; 234 235 case CALL_EXPR: 236 case MODIFY_EXPR: 237 /* These are valid regardless of their type. */ 238 return true; 239 240 default: 241 return false; 242 } 243} 244 245/* Return true if T is a variable. */ 246 247bool 248is_gimple_variable (tree t) 249{ 250 return (TREE_CODE (t) == VAR_DECL 251 || TREE_CODE (t) == PARM_DECL 252 || TREE_CODE (t) == RESULT_DECL 253 || TREE_CODE (t) == SSA_NAME); 254} 255 256/* Return true if T is a GIMPLE identifier (something with an address). */ 257 258bool 259is_gimple_id (tree t) 260{ 261 return (is_gimple_variable (t) 262 || TREE_CODE (t) == FUNCTION_DECL 263 || TREE_CODE (t) == LABEL_DECL 264 || TREE_CODE (t) == CONST_DECL 265 /* Allow string constants, since they are addressable. */ 266 || TREE_CODE (t) == STRING_CST); 267} 268 269/* Return true if TYPE is a suitable type for a scalar register variable. */ 270 271bool 272is_gimple_reg_type (tree type) 273{ 274 return !AGGREGATE_TYPE_P (type); 275} 276 277/* Return true if T is a non-aggregate register variable. */ 278 279bool 280is_gimple_reg (tree t) 281{ 282 if (TREE_CODE (t) == SSA_NAME) 283 t = SSA_NAME_VAR (t); 284 285 if (MTAG_P (t)) 286 return false; 287 288 if (!is_gimple_variable (t)) 289 return false; 290 291 if (!is_gimple_reg_type (TREE_TYPE (t))) 292 return false; 293 294 /* A volatile decl is not acceptable because we can't reuse it as 295 needed. We need to copy it into a temp first. */ 296 if (TREE_THIS_VOLATILE (t)) 297 return false; 298 299 /* We define "registers" as things that can be renamed as needed, 300 which with our infrastructure does not apply to memory. */ 301 if (needs_to_live_in_memory (t)) 302 return false; 303 304 /* Hard register variables are an interesting case. For those that 305 are call-clobbered, we don't know where all the calls are, since 306 we don't (want to) take into account which operations will turn 307 into libcalls at the rtl level. For those that are call-saved, 308 we don't currently model the fact that calls may in fact change 309 global hard registers, nor do we examine ASM_CLOBBERS at the tree 310 level, and so miss variable changes that might imply. All around, 311 it seems safest to not do too much optimization with these at the 312 tree level at all. We'll have to rely on the rtl optimizers to 313 clean this up, as there we've got all the appropriate bits exposed. */ 314 if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t)) 315 return false; 316 317 /* Complex values must have been put into ssa form. That is, no 318 assignments to the individual components. */ 319 if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE) 320 return DECL_COMPLEX_GIMPLE_REG_P (t); 321 322 return true; 323} 324 325 326/* Returns true if T is a GIMPLE formal temporary variable. */ 327 328bool 329is_gimple_formal_tmp_var (tree t) 330{ 331 if (TREE_CODE (t) == SSA_NAME) 332 return true; 333 334 return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t); 335} 336 337/* Returns true if T is a GIMPLE formal temporary register variable. */ 338 339bool 340is_gimple_formal_tmp_reg (tree t) 341{ 342 /* The intent of this is to get hold of a value that won't change. 343 An SSA_NAME qualifies no matter if its of a user variable or not. */ 344 if (TREE_CODE (t) == SSA_NAME) 345 return true; 346 347 /* We don't know the lifetime characteristics of user variables. */ 348 if (!is_gimple_formal_tmp_var (t)) 349 return false; 350 351 /* Finally, it must be capable of being placed in a register. */ 352 return is_gimple_reg (t); 353} 354 355/* Return true if T is a GIMPLE variable whose address is not needed. */ 356 357bool 358is_gimple_non_addressable (tree t) 359{ 360 if (TREE_CODE (t) == SSA_NAME) 361 t = SSA_NAME_VAR (t); 362 363 return (is_gimple_variable (t) && ! needs_to_live_in_memory (t)); 364} 365 366/* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant. */ 367 368bool 369is_gimple_val (tree t) 370{ 371 /* Make loads from volatiles and memory vars explicit. */ 372 if (is_gimple_variable (t) 373 && is_gimple_reg_type (TREE_TYPE (t)) 374 && !is_gimple_reg (t)) 375 return false; 376 377 /* FIXME make these decls. That can happen only when we expose the 378 entire landing-pad construct at the tree level. */ 379 if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR) 380 return 1; 381 382 return (is_gimple_variable (t) || is_gimple_min_invariant (t)); 383} 384 385/* Similarly, but accept hard registers as inputs to asm statements. */ 386 387bool 388is_gimple_asm_val (tree t) 389{ 390 if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t)) 391 return true; 392 393 return is_gimple_val (t); 394} 395 396/* Return true if T is a GIMPLE minimal lvalue. */ 397 398bool 399is_gimple_min_lval (tree t) 400{ 401 return (is_gimple_id (t) 402 || TREE_CODE (t) == INDIRECT_REF); 403} 404 405/* Return true if T is a typecast operation. */ 406 407bool 408is_gimple_cast (tree t) 409{ 410 return (TREE_CODE (t) == NOP_EXPR 411 || TREE_CODE (t) == CONVERT_EXPR 412 || TREE_CODE (t) == FIX_TRUNC_EXPR 413 || TREE_CODE (t) == FIX_CEIL_EXPR 414 || TREE_CODE (t) == FIX_FLOOR_EXPR 415 || TREE_CODE (t) == FIX_ROUND_EXPR); 416} 417 418/* Return true if T is a valid op0 of a CALL_EXPR. */ 419 420bool 421is_gimple_call_addr (tree t) 422{ 423 return (TREE_CODE (t) == OBJ_TYPE_REF 424 || is_gimple_val (t)); 425} 426 427/* If T makes a function call, return the corresponding CALL_EXPR operand. 428 Otherwise, return NULL_TREE. */ 429 430tree 431get_call_expr_in (tree t) 432{ 433 if (TREE_CODE (t) == MODIFY_EXPR) 434 t = TREE_OPERAND (t, 1); 435 if (TREE_CODE (t) == WITH_SIZE_EXPR) 436 t = TREE_OPERAND (t, 0); 437 if (TREE_CODE (t) == CALL_EXPR) 438 return t; 439 return NULL_TREE; 440} 441 442/* Given a memory reference expression T, return its base address. 443 The base address of a memory reference expression is the main 444 object being referenced. For instance, the base address for 445 'array[i].fld[j]' is 'array'. You can think of this as stripping 446 away the offset part from a memory address. 447 448 This function calls handled_component_p to strip away all the inner 449 parts of the memory reference until it reaches the base object. */ 450 451tree 452get_base_address (tree t) 453{ 454 while (handled_component_p (t)) 455 t = TREE_OPERAND (t, 0); 456 457 if (SSA_VAR_P (t) 458 || TREE_CODE (t) == STRING_CST 459 || TREE_CODE (t) == CONSTRUCTOR 460 || INDIRECT_REF_P (t)) 461 return t; 462 else 463 return NULL_TREE; 464} 465 466void 467recalculate_side_effects (tree t) 468{ 469 enum tree_code code = TREE_CODE (t); 470 int len = TREE_CODE_LENGTH (code); 471 int i; 472 473 switch (TREE_CODE_CLASS (code)) 474 { 475 case tcc_expression: 476 switch (code) 477 { 478 case INIT_EXPR: 479 case MODIFY_EXPR: 480 case VA_ARG_EXPR: 481 case PREDECREMENT_EXPR: 482 case PREINCREMENT_EXPR: 483 case POSTDECREMENT_EXPR: 484 case POSTINCREMENT_EXPR: 485 /* All of these have side-effects, no matter what their 486 operands are. */ 487 return; 488 489 default: 490 break; 491 } 492 /* Fall through. */ 493 494 case tcc_comparison: /* a comparison expression */ 495 case tcc_unary: /* a unary arithmetic expression */ 496 case tcc_binary: /* a binary arithmetic expression */ 497 case tcc_reference: /* a reference */ 498 TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t); 499 for (i = 0; i < len; ++i) 500 { 501 tree op = TREE_OPERAND (t, i); 502 if (op && TREE_SIDE_EFFECTS (op)) 503 TREE_SIDE_EFFECTS (t) = 1; 504 } 505 break; 506 507 default: 508 /* Can never be used with non-expressions. */ 509 gcc_unreachable (); 510 } 511} 512