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 return is_gimple_val (t); 120 else 121 return is_gimple_formal_tmp_rhs (t); 122} 123 124/* Returns the appropriate RHS predicate for this LHS. */ 125 126gimple_predicate 127rhs_predicate_for (tree lhs) 128{ 129 if (is_gimple_formal_tmp_var (lhs)) 130 return is_gimple_formal_tmp_rhs; 131 else if (is_gimple_reg (lhs)) 132 return is_gimple_reg_rhs; 133 else 134 return is_gimple_mem_rhs; 135} 136 137/* Return true if T is a valid LHS for a GIMPLE assignment expression. */ 138 139bool 140is_gimple_lvalue (tree t) 141{ 142 return (is_gimple_addressable (t) 143 || TREE_CODE (t) == WITH_SIZE_EXPR 144 /* These are complex lvalues, but don't have addresses, so they 145 go here. */ 146 || TREE_CODE (t) == BIT_FIELD_REF); 147} 148 149/* Return true if T is a GIMPLE condition. */ 150 151bool 152is_gimple_condexpr (tree t) 153{ 154 return (is_gimple_val (t) || COMPARISON_CLASS_P (t)); 155} 156 157/* Return true if T is something whose address can be taken. */ 158 159bool 160is_gimple_addressable (tree t) 161{ 162 return (is_gimple_id (t) || handled_component_p (t) 163 || INDIRECT_REF_P (t)); 164} 165 166/* Return true if T is function invariant. Or rather a restricted 167 form of function invariant. */ 168 169bool 170is_gimple_min_invariant (tree t) 171{ 172 switch (TREE_CODE (t)) 173 { 174 case ADDR_EXPR: 175 return TREE_INVARIANT (t); 176 177 case INTEGER_CST: 178 case REAL_CST: 179 case STRING_CST: 180 case COMPLEX_CST: 181 case VECTOR_CST: 182 return true; 183 184 default: 185 return false; 186 } 187} 188 189/* Return true if T looks like a valid GIMPLE statement. */ 190 191bool 192is_gimple_stmt (tree t) 193{ 194 enum tree_code code = TREE_CODE (t); 195 196 if (IS_EMPTY_STMT (t)) 197 return 1; 198 199 switch (code) 200 { 201 case BIND_EXPR: 202 case COND_EXPR: 203 /* These are only valid if they're void. */ 204 return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t)); 205 206 case SWITCH_EXPR: 207 case GOTO_EXPR: 208 case RETURN_EXPR: 209 case LABEL_EXPR: 210 case CASE_LABEL_EXPR: 211 case TRY_CATCH_EXPR: 212 case TRY_FINALLY_EXPR: 213 case EH_FILTER_EXPR: 214 case CATCH_EXPR: 215 case ASM_EXPR: 216 case RESX_EXPR: 217 case PHI_NODE: 218 case STATEMENT_LIST: 219 /* These are always void. */ 220 return true; 221 222 case CALL_EXPR: 223 case MODIFY_EXPR: 224 /* These are valid regardless of their type. */ 225 return true; 226 227 default: 228 return false; 229 } 230} 231 232/* Return true if T is a variable. */ 233 234bool 235is_gimple_variable (tree t) 236{ 237 return (TREE_CODE (t) == VAR_DECL 238 || TREE_CODE (t) == PARM_DECL 239 || TREE_CODE (t) == RESULT_DECL 240 || TREE_CODE (t) == SSA_NAME); 241} 242 243/* Return true if T is a GIMPLE identifier (something with an address). */ 244 245bool 246is_gimple_id (tree t) 247{ 248 return (is_gimple_variable (t) 249 || TREE_CODE (t) == FUNCTION_DECL 250 || TREE_CODE (t) == LABEL_DECL 251 || TREE_CODE (t) == CONST_DECL 252 /* Allow string constants, since they are addressable. */ 253 || TREE_CODE (t) == STRING_CST); 254} 255 256/* Return true if TYPE is a suitable type for a scalar register variable. */ 257 258bool 259is_gimple_reg_type (tree type) 260{ 261 return !AGGREGATE_TYPE_P (type); 262} 263 264/* Return true if T is a non-aggregate register variable. */ 265 266bool 267is_gimple_reg (tree t) 268{ 269 var_ann_t ann; 270 271 if (TREE_CODE (t) == SSA_NAME) 272 t = SSA_NAME_VAR (t); 273 274 if (!is_gimple_variable (t)) 275 return false; 276 277 if (!is_gimple_reg_type (TREE_TYPE (t))) 278 return false; 279 280 /* A volatile decl is not acceptable because we can't reuse it as 281 needed. We need to copy it into a temp first. */ 282 if (TREE_THIS_VOLATILE (t)) 283 return false; 284 285 /* We define "registers" as things that can be renamed as needed, 286 which with our infrastructure does not apply to memory. */ 287 if (needs_to_live_in_memory (t)) 288 return false; 289 290 /* Hard register variables are an interesting case. For those that 291 are call-clobbered, we don't know where all the calls are, since 292 we don't (want to) take into account which operations will turn 293 into libcalls at the rtl level. For those that are call-saved, 294 we don't currently model the fact that calls may in fact change 295 global hard registers, nor do we examine ASM_CLOBBERS at the tree 296 level, and so miss variable changes that might imply. All around, 297 it seems safest to not do too much optimization with these at the 298 tree level at all. We'll have to rely on the rtl optimizers to 299 clean this up, as there we've got all the appropriate bits exposed. */ 300 if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t)) 301 return false; 302 303 /* Complex values must have been put into ssa form. That is, no 304 assignments to the individual components. */ 305 if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE) 306 return DECL_COMPLEX_GIMPLE_REG_P (t); 307 308 /* Some compiler temporaries are created to be used exclusively in 309 virtual operands (currently memory tags and sub-variables). 310 These variables should never be considered GIMPLE registers. */ 311 if (DECL_ARTIFICIAL (t) && (ann = var_ann (t)) != NULL) 312 return ann->mem_tag_kind == NOT_A_TAG; 313 314 return true; 315} 316 317 318/* Returns true if T is a GIMPLE formal temporary variable. */ 319 320bool 321is_gimple_formal_tmp_var (tree t) 322{ 323 if (TREE_CODE (t) == SSA_NAME) 324 return true; 325 326 return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t); 327} 328 329/* Returns true if T is a GIMPLE formal temporary register variable. */ 330 331bool 332is_gimple_formal_tmp_reg (tree t) 333{ 334 /* The intent of this is to get hold of a value that won't change. 335 An SSA_NAME qualifies no matter if its of a user variable or not. */ 336 if (TREE_CODE (t) == SSA_NAME) 337 return true; 338 339 /* We don't know the lifetime characteristics of user variables. */ 340 if (!is_gimple_formal_tmp_var (t)) 341 return false; 342 343 /* Finally, it must be capable of being placed in a register. */ 344 return is_gimple_reg (t); 345} 346 347/* Return true if T is a GIMPLE variable whose address is not needed. */ 348 349bool 350is_gimple_non_addressable (tree t) 351{ 352 if (TREE_CODE (t) == SSA_NAME) 353 t = SSA_NAME_VAR (t); 354 355 return (is_gimple_variable (t) && ! needs_to_live_in_memory (t)); 356} 357 358/* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant. */ 359 360bool 361is_gimple_val (tree t) 362{ 363 /* Make loads from volatiles and memory vars explicit. */ 364 if (is_gimple_variable (t) 365 && is_gimple_reg_type (TREE_TYPE (t)) 366 && !is_gimple_reg (t)) 367 return false; 368 369 /* FIXME make these decls. That can happen only when we expose the 370 entire landing-pad construct at the tree level. */ 371 if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR) 372 return 1; 373 374 return (is_gimple_variable (t) || is_gimple_min_invariant (t)); 375} 376 377/* Similarly, but accept hard registers as inputs to asm statements. */ 378 379bool 380is_gimple_asm_val (tree t) 381{ 382 if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t)) 383 return true; 384 385 return is_gimple_val (t); 386} 387 388/* Return true if T is a GIMPLE minimal lvalue. */ 389 390bool 391is_gimple_min_lval (tree t) 392{ 393 return (is_gimple_id (t) 394 || TREE_CODE (t) == INDIRECT_REF); 395} 396 397/* Return true if T is a typecast operation. */ 398 399bool 400is_gimple_cast (tree t) 401{ 402 return (TREE_CODE (t) == NOP_EXPR 403 || TREE_CODE (t) == CONVERT_EXPR 404 || TREE_CODE (t) == FIX_TRUNC_EXPR 405 || TREE_CODE (t) == FIX_CEIL_EXPR 406 || TREE_CODE (t) == FIX_FLOOR_EXPR 407 || TREE_CODE (t) == FIX_ROUND_EXPR); 408} 409 410/* Return true if T is a valid op0 of a CALL_EXPR. */ 411 412bool 413is_gimple_call_addr (tree t) 414{ 415 return (TREE_CODE (t) == OBJ_TYPE_REF 416 || is_gimple_val (t)); 417} 418 419/* If T makes a function call, return the corresponding CALL_EXPR operand. 420 Otherwise, return NULL_TREE. */ 421 422tree 423get_call_expr_in (tree t) 424{ 425 if (TREE_CODE (t) == MODIFY_EXPR) 426 t = TREE_OPERAND (t, 1); 427 if (TREE_CODE (t) == WITH_SIZE_EXPR) 428 t = TREE_OPERAND (t, 0); 429 if (TREE_CODE (t) == CALL_EXPR) 430 return t; 431 return NULL_TREE; 432} 433 434/* Given a memory reference expression T, return its base address. 435 The base address of a memory reference expression is the main 436 object being referenced. For instance, the base address for 437 'array[i].fld[j]' is 'array'. You can think of this as stripping 438 away the offset part from a memory address. 439 440 This function calls handled_component_p to strip away all the inner 441 parts of the memory reference until it reaches the base object. */ 442 443tree 444get_base_address (tree t) 445{ 446 while (handled_component_p (t)) 447 t = TREE_OPERAND (t, 0); 448 449 if (SSA_VAR_P (t) 450 || TREE_CODE (t) == STRING_CST 451 || TREE_CODE (t) == CONSTRUCTOR 452 || INDIRECT_REF_P (t)) 453 return t; 454 else 455 return NULL_TREE; 456} 457 458void 459recalculate_side_effects (tree t) 460{ 461 enum tree_code code = TREE_CODE (t); 462 int len = TREE_CODE_LENGTH (code); 463 int i; 464 465 switch (TREE_CODE_CLASS (code)) 466 { 467 case tcc_expression: 468 switch (code) 469 { 470 case INIT_EXPR: 471 case MODIFY_EXPR: 472 case VA_ARG_EXPR: 473 case PREDECREMENT_EXPR: 474 case PREINCREMENT_EXPR: 475 case POSTDECREMENT_EXPR: 476 case POSTINCREMENT_EXPR: 477 /* All of these have side-effects, no matter what their 478 operands are. */ 479 return; 480 481 default: 482 break; 483 } 484 /* Fall through. */ 485 486 case tcc_comparison: /* a comparison expression */ 487 case tcc_unary: /* a unary arithmetic expression */ 488 case tcc_binary: /* a binary arithmetic expression */ 489 case tcc_reference: /* a reference */ 490 TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t); 491 for (i = 0; i < len; ++i) 492 { 493 tree op = TREE_OPERAND (t, i); 494 if (op && TREE_SIDE_EFFECTS (op)) 495 TREE_SIDE_EFFECTS (t) = 1; 496 } 497 break; 498 499 default: 500 /* Can never be used with non-expressions. */ 501 gcc_unreachable (); 502 } 503} 504