1169689Skan/* Functions to analyze and validate GIMPLE trees. 2169689Skan Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 3169689Skan Contributed by Diego Novillo <dnovillo@redhat.com> 4169689Skan Rewritten by Jason Merrill <jason@redhat.com> 5169689Skan 6169689SkanThis file is part of GCC. 7169689Skan 8169689SkanGCC is free software; you can redistribute it and/or modify 9169689Skanit under the terms of the GNU General Public License as published by 10169689Skanthe Free Software Foundation; either version 2, or (at your option) 11169689Skanany later version. 12169689Skan 13169689SkanGCC is distributed in the hope that it will be useful, 14169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 15169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16169689SkanGNU General Public License for more details. 17169689Skan 18169689SkanYou should have received a copy of the GNU General Public License 19169689Skanalong with GCC; see the file COPYING. If not, write to 20169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 21169689SkanBoston, MA 02110-1301, USA. */ 22169689Skan 23169689Skan#include "config.h" 24169689Skan#include "system.h" 25169689Skan#include "coretypes.h" 26169689Skan#include "ggc.h" 27169689Skan#include "tm.h" 28169689Skan#include "tree.h" 29169689Skan#include "tree-gimple.h" 30169689Skan#include "tree-flow.h" 31169689Skan#include "output.h" 32169689Skan#include "rtl.h" 33169689Skan#include "expr.h" 34169689Skan#include "bitmap.h" 35169689Skan 36169689Skan/* For the definitive definition of GIMPLE, see doc/tree-ssa.texi. */ 37169689Skan 38169689Skan/* Validation of GIMPLE expressions. */ 39169689Skan 40169689Skan/* Return true if T is a GIMPLE RHS for an assignment to a temporary. */ 41169689Skan 42169689Skanbool 43169689Skanis_gimple_formal_tmp_rhs (tree t) 44169689Skan{ 45169689Skan enum tree_code code = TREE_CODE (t); 46169689Skan 47169689Skan switch (TREE_CODE_CLASS (code)) 48169689Skan { 49169689Skan case tcc_unary: 50169689Skan case tcc_binary: 51169689Skan case tcc_comparison: 52169689Skan return true; 53169689Skan 54169689Skan default: 55169689Skan break; 56169689Skan } 57169689Skan 58169689Skan switch (code) 59169689Skan { 60169689Skan case TRUTH_NOT_EXPR: 61169689Skan case TRUTH_AND_EXPR: 62169689Skan case TRUTH_OR_EXPR: 63169689Skan case TRUTH_XOR_EXPR: 64169689Skan case ADDR_EXPR: 65169689Skan case CALL_EXPR: 66169689Skan case CONSTRUCTOR: 67169689Skan case COMPLEX_EXPR: 68169689Skan case INTEGER_CST: 69169689Skan case REAL_CST: 70169689Skan case STRING_CST: 71169689Skan case COMPLEX_CST: 72169689Skan case VECTOR_CST: 73169689Skan case OBJ_TYPE_REF: 74169689Skan case ASSERT_EXPR: 75169689Skan return true; 76169689Skan 77169689Skan default: 78169689Skan break; 79169689Skan } 80169689Skan 81169689Skan return is_gimple_lvalue (t) || is_gimple_val (t); 82169689Skan} 83169689Skan 84169689Skan/* Returns true iff T is a valid RHS for an assignment to a renamed 85169689Skan user -- or front-end generated artificial -- variable. */ 86169689Skan 87169689Skanbool 88169689Skanis_gimple_reg_rhs (tree t) 89169689Skan{ 90169689Skan /* If the RHS of the MODIFY_EXPR may throw or make a nonlocal goto 91169689Skan and the LHS is a user variable, then we need to introduce a formal 92169689Skan temporary. This way the optimizers can determine that the user 93169689Skan variable is only modified if evaluation of the RHS does not throw. 94169689Skan 95169689Skan Don't force a temp of a non-renamable type; the copy could be 96169689Skan arbitrarily expensive. Instead we will generate a V_MAY_DEF for 97169689Skan the assignment. */ 98169689Skan 99169689Skan if (is_gimple_reg_type (TREE_TYPE (t)) 100169689Skan && ((TREE_CODE (t) == CALL_EXPR && TREE_SIDE_EFFECTS (t)) 101169689Skan || tree_could_throw_p (t))) 102169689Skan return false; 103169689Skan 104169689Skan return is_gimple_formal_tmp_rhs (t); 105169689Skan} 106169689Skan 107169689Skan/* Returns true iff T is a valid RHS for an assignment to an un-renamed 108169689Skan LHS, or for a call argument. */ 109169689Skan 110169689Skanbool 111169689Skanis_gimple_mem_rhs (tree t) 112169689Skan{ 113169689Skan /* If we're dealing with a renamable type, either source or dest must be 114169689Skan a renamed variable. Also force a temporary if the type doesn't need 115169689Skan to be stored in memory, since it's cheap and prevents erroneous 116169689Skan tailcalls (PR 17526). */ 117169689Skan if (is_gimple_reg_type (TREE_TYPE (t)) 118169689Skan || (TYPE_MODE (TREE_TYPE (t)) != BLKmode 119169689Skan && (TREE_CODE (t) != CALL_EXPR 120169689Skan || ! aggregate_value_p (t, t)))) 121169689Skan return is_gimple_val (t); 122169689Skan else 123169689Skan return is_gimple_formal_tmp_rhs (t); 124169689Skan} 125169689Skan 126169689Skan/* Returns the appropriate RHS predicate for this LHS. */ 127169689Skan 128169689Skangimple_predicate 129169689Skanrhs_predicate_for (tree lhs) 130169689Skan{ 131169689Skan if (is_gimple_formal_tmp_var (lhs)) 132169689Skan return is_gimple_formal_tmp_rhs; 133169689Skan else if (is_gimple_reg (lhs)) 134169689Skan return is_gimple_reg_rhs; 135169689Skan else 136169689Skan return is_gimple_mem_rhs; 137169689Skan} 138169689Skan 139169689Skan/* Return true if T is a valid LHS for a GIMPLE assignment expression. */ 140169689Skan 141169689Skanbool 142169689Skanis_gimple_lvalue (tree t) 143169689Skan{ 144169689Skan return (is_gimple_addressable (t) 145169689Skan || TREE_CODE (t) == WITH_SIZE_EXPR 146169689Skan /* These are complex lvalues, but don't have addresses, so they 147169689Skan go here. */ 148169689Skan || TREE_CODE (t) == BIT_FIELD_REF); 149169689Skan} 150169689Skan 151169689Skan/* Return true if T is a GIMPLE condition. */ 152169689Skan 153169689Skanbool 154169689Skanis_gimple_condexpr (tree t) 155169689Skan{ 156169689Skan return (is_gimple_val (t) || COMPARISON_CLASS_P (t)); 157169689Skan} 158169689Skan 159169689Skan/* Return true if T is something whose address can be taken. */ 160169689Skan 161169689Skanbool 162169689Skanis_gimple_addressable (tree t) 163169689Skan{ 164169689Skan return (is_gimple_id (t) || handled_component_p (t) 165169689Skan || INDIRECT_REF_P (t)); 166169689Skan} 167169689Skan 168169689Skan/* Return true if T is function invariant. Or rather a restricted 169169689Skan form of function invariant. */ 170169689Skan 171169689Skanbool 172169689Skanis_gimple_min_invariant (tree t) 173169689Skan{ 174169689Skan switch (TREE_CODE (t)) 175169689Skan { 176169689Skan case ADDR_EXPR: 177169689Skan return TREE_INVARIANT (t); 178169689Skan 179169689Skan case INTEGER_CST: 180169689Skan case REAL_CST: 181169689Skan case STRING_CST: 182169689Skan case COMPLEX_CST: 183169689Skan case VECTOR_CST: 184169689Skan return true; 185169689Skan 186169689Skan default: 187169689Skan return false; 188169689Skan } 189169689Skan} 190169689Skan 191169689Skan/* Return true if T looks like a valid GIMPLE statement. */ 192169689Skan 193169689Skanbool 194169689Skanis_gimple_stmt (tree t) 195169689Skan{ 196169689Skan enum tree_code code = TREE_CODE (t); 197169689Skan 198169689Skan switch (code) 199169689Skan { 200169689Skan case NOP_EXPR: 201169689Skan /* The only valid NOP_EXPR is the empty statement. */ 202169689Skan return IS_EMPTY_STMT (t); 203169689Skan 204169689Skan case BIND_EXPR: 205169689Skan case COND_EXPR: 206169689Skan /* These are only valid if they're void. */ 207169689Skan return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t)); 208169689Skan 209169689Skan case SWITCH_EXPR: 210169689Skan case GOTO_EXPR: 211169689Skan case RETURN_EXPR: 212169689Skan case LABEL_EXPR: 213169689Skan case CASE_LABEL_EXPR: 214169689Skan case TRY_CATCH_EXPR: 215169689Skan case TRY_FINALLY_EXPR: 216169689Skan case EH_FILTER_EXPR: 217169689Skan case CATCH_EXPR: 218169689Skan case ASM_EXPR: 219169689Skan case RESX_EXPR: 220169689Skan case PHI_NODE: 221169689Skan case STATEMENT_LIST: 222169689Skan case OMP_PARALLEL: 223169689Skan case OMP_FOR: 224169689Skan case OMP_SECTIONS: 225169689Skan case OMP_SECTION: 226169689Skan case OMP_SINGLE: 227169689Skan case OMP_MASTER: 228169689Skan case OMP_ORDERED: 229169689Skan case OMP_CRITICAL: 230169689Skan case OMP_RETURN: 231169689Skan case OMP_CONTINUE: 232169689Skan /* These are always void. */ 233169689Skan return true; 234169689Skan 235169689Skan case CALL_EXPR: 236169689Skan case MODIFY_EXPR: 237169689Skan /* These are valid regardless of their type. */ 238169689Skan return true; 239169689Skan 240169689Skan default: 241169689Skan return false; 242169689Skan } 243169689Skan} 244169689Skan 245169689Skan/* Return true if T is a variable. */ 246169689Skan 247169689Skanbool 248169689Skanis_gimple_variable (tree t) 249169689Skan{ 250169689Skan return (TREE_CODE (t) == VAR_DECL 251169689Skan || TREE_CODE (t) == PARM_DECL 252169689Skan || TREE_CODE (t) == RESULT_DECL 253169689Skan || TREE_CODE (t) == SSA_NAME); 254169689Skan} 255169689Skan 256169689Skan/* Return true if T is a GIMPLE identifier (something with an address). */ 257169689Skan 258169689Skanbool 259169689Skanis_gimple_id (tree t) 260169689Skan{ 261169689Skan return (is_gimple_variable (t) 262169689Skan || TREE_CODE (t) == FUNCTION_DECL 263169689Skan || TREE_CODE (t) == LABEL_DECL 264169689Skan || TREE_CODE (t) == CONST_DECL 265169689Skan /* Allow string constants, since they are addressable. */ 266169689Skan || TREE_CODE (t) == STRING_CST); 267169689Skan} 268169689Skan 269169689Skan/* Return true if TYPE is a suitable type for a scalar register variable. */ 270169689Skan 271169689Skanbool 272169689Skanis_gimple_reg_type (tree type) 273169689Skan{ 274169689Skan return !AGGREGATE_TYPE_P (type); 275169689Skan} 276169689Skan 277169689Skan/* Return true if T is a non-aggregate register variable. */ 278169689Skan 279169689Skanbool 280169689Skanis_gimple_reg (tree t) 281169689Skan{ 282169689Skan if (TREE_CODE (t) == SSA_NAME) 283169689Skan t = SSA_NAME_VAR (t); 284169689Skan 285169689Skan if (MTAG_P (t)) 286169689Skan return false; 287169689Skan 288169689Skan if (!is_gimple_variable (t)) 289169689Skan return false; 290169689Skan 291169689Skan if (!is_gimple_reg_type (TREE_TYPE (t))) 292169689Skan return false; 293169689Skan 294169689Skan /* A volatile decl is not acceptable because we can't reuse it as 295169689Skan needed. We need to copy it into a temp first. */ 296169689Skan if (TREE_THIS_VOLATILE (t)) 297169689Skan return false; 298169689Skan 299169689Skan /* We define "registers" as things that can be renamed as needed, 300169689Skan which with our infrastructure does not apply to memory. */ 301169689Skan if (needs_to_live_in_memory (t)) 302169689Skan return false; 303169689Skan 304169689Skan /* Hard register variables are an interesting case. For those that 305169689Skan are call-clobbered, we don't know where all the calls are, since 306169689Skan we don't (want to) take into account which operations will turn 307169689Skan into libcalls at the rtl level. For those that are call-saved, 308169689Skan we don't currently model the fact that calls may in fact change 309169689Skan global hard registers, nor do we examine ASM_CLOBBERS at the tree 310169689Skan level, and so miss variable changes that might imply. All around, 311169689Skan it seems safest to not do too much optimization with these at the 312169689Skan tree level at all. We'll have to rely on the rtl optimizers to 313169689Skan clean this up, as there we've got all the appropriate bits exposed. */ 314169689Skan if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t)) 315169689Skan return false; 316169689Skan 317169689Skan /* Complex values must have been put into ssa form. That is, no 318169689Skan assignments to the individual components. */ 319169689Skan if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE) 320169689Skan return DECL_COMPLEX_GIMPLE_REG_P (t); 321169689Skan 322169689Skan return true; 323169689Skan} 324169689Skan 325169689Skan 326169689Skan/* Returns true if T is a GIMPLE formal temporary variable. */ 327169689Skan 328169689Skanbool 329169689Skanis_gimple_formal_tmp_var (tree t) 330169689Skan{ 331169689Skan if (TREE_CODE (t) == SSA_NAME) 332169689Skan return true; 333169689Skan 334169689Skan return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t); 335169689Skan} 336169689Skan 337169689Skan/* Returns true if T is a GIMPLE formal temporary register variable. */ 338169689Skan 339169689Skanbool 340169689Skanis_gimple_formal_tmp_reg (tree t) 341169689Skan{ 342169689Skan /* The intent of this is to get hold of a value that won't change. 343169689Skan An SSA_NAME qualifies no matter if its of a user variable or not. */ 344169689Skan if (TREE_CODE (t) == SSA_NAME) 345169689Skan return true; 346169689Skan 347169689Skan /* We don't know the lifetime characteristics of user variables. */ 348169689Skan if (!is_gimple_formal_tmp_var (t)) 349169689Skan return false; 350169689Skan 351169689Skan /* Finally, it must be capable of being placed in a register. */ 352169689Skan return is_gimple_reg (t); 353169689Skan} 354169689Skan 355169689Skan/* Return true if T is a GIMPLE variable whose address is not needed. */ 356169689Skan 357169689Skanbool 358169689Skanis_gimple_non_addressable (tree t) 359169689Skan{ 360169689Skan if (TREE_CODE (t) == SSA_NAME) 361169689Skan t = SSA_NAME_VAR (t); 362169689Skan 363169689Skan return (is_gimple_variable (t) && ! needs_to_live_in_memory (t)); 364169689Skan} 365169689Skan 366169689Skan/* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant. */ 367169689Skan 368169689Skanbool 369169689Skanis_gimple_val (tree t) 370169689Skan{ 371169689Skan /* Make loads from volatiles and memory vars explicit. */ 372169689Skan if (is_gimple_variable (t) 373169689Skan && is_gimple_reg_type (TREE_TYPE (t)) 374169689Skan && !is_gimple_reg (t)) 375169689Skan return false; 376169689Skan 377169689Skan /* FIXME make these decls. That can happen only when we expose the 378169689Skan entire landing-pad construct at the tree level. */ 379169689Skan if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR) 380169689Skan return 1; 381169689Skan 382169689Skan return (is_gimple_variable (t) || is_gimple_min_invariant (t)); 383169689Skan} 384169689Skan 385169689Skan/* Similarly, but accept hard registers as inputs to asm statements. */ 386169689Skan 387169689Skanbool 388169689Skanis_gimple_asm_val (tree t) 389169689Skan{ 390169689Skan if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t)) 391169689Skan return true; 392169689Skan 393169689Skan return is_gimple_val (t); 394169689Skan} 395169689Skan 396169689Skan/* Return true if T is a GIMPLE minimal lvalue. */ 397169689Skan 398169689Skanbool 399169689Skanis_gimple_min_lval (tree t) 400169689Skan{ 401169689Skan return (is_gimple_id (t) 402169689Skan || TREE_CODE (t) == INDIRECT_REF); 403169689Skan} 404169689Skan 405169689Skan/* Return true if T is a typecast operation. */ 406169689Skan 407169689Skanbool 408169689Skanis_gimple_cast (tree t) 409169689Skan{ 410169689Skan return (TREE_CODE (t) == NOP_EXPR 411169689Skan || TREE_CODE (t) == CONVERT_EXPR 412169689Skan || TREE_CODE (t) == FIX_TRUNC_EXPR 413169689Skan || TREE_CODE (t) == FIX_CEIL_EXPR 414169689Skan || TREE_CODE (t) == FIX_FLOOR_EXPR 415169689Skan || TREE_CODE (t) == FIX_ROUND_EXPR); 416169689Skan} 417169689Skan 418169689Skan/* Return true if T is a valid op0 of a CALL_EXPR. */ 419169689Skan 420169689Skanbool 421169689Skanis_gimple_call_addr (tree t) 422169689Skan{ 423169689Skan return (TREE_CODE (t) == OBJ_TYPE_REF 424169689Skan || is_gimple_val (t)); 425169689Skan} 426169689Skan 427169689Skan/* If T makes a function call, return the corresponding CALL_EXPR operand. 428169689Skan Otherwise, return NULL_TREE. */ 429169689Skan 430169689Skantree 431169689Skanget_call_expr_in (tree t) 432169689Skan{ 433169689Skan if (TREE_CODE (t) == MODIFY_EXPR) 434169689Skan t = TREE_OPERAND (t, 1); 435169689Skan if (TREE_CODE (t) == WITH_SIZE_EXPR) 436169689Skan t = TREE_OPERAND (t, 0); 437169689Skan if (TREE_CODE (t) == CALL_EXPR) 438169689Skan return t; 439169689Skan return NULL_TREE; 440169689Skan} 441169689Skan 442169689Skan/* Given a memory reference expression T, return its base address. 443169689Skan The base address of a memory reference expression is the main 444169689Skan object being referenced. For instance, the base address for 445169689Skan 'array[i].fld[j]' is 'array'. You can think of this as stripping 446169689Skan away the offset part from a memory address. 447169689Skan 448169689Skan This function calls handled_component_p to strip away all the inner 449169689Skan parts of the memory reference until it reaches the base object. */ 450169689Skan 451169689Skantree 452169689Skanget_base_address (tree t) 453169689Skan{ 454169689Skan while (handled_component_p (t)) 455169689Skan t = TREE_OPERAND (t, 0); 456169689Skan 457169689Skan if (SSA_VAR_P (t) 458169689Skan || TREE_CODE (t) == STRING_CST 459169689Skan || TREE_CODE (t) == CONSTRUCTOR 460169689Skan || INDIRECT_REF_P (t)) 461169689Skan return t; 462169689Skan else 463169689Skan return NULL_TREE; 464169689Skan} 465169689Skan 466169689Skanvoid 467169689Skanrecalculate_side_effects (tree t) 468169689Skan{ 469169689Skan enum tree_code code = TREE_CODE (t); 470169689Skan int len = TREE_CODE_LENGTH (code); 471169689Skan int i; 472169689Skan 473169689Skan switch (TREE_CODE_CLASS (code)) 474169689Skan { 475169689Skan case tcc_expression: 476169689Skan switch (code) 477169689Skan { 478169689Skan case INIT_EXPR: 479169689Skan case MODIFY_EXPR: 480169689Skan case VA_ARG_EXPR: 481169689Skan case PREDECREMENT_EXPR: 482169689Skan case PREINCREMENT_EXPR: 483169689Skan case POSTDECREMENT_EXPR: 484169689Skan case POSTINCREMENT_EXPR: 485169689Skan /* All of these have side-effects, no matter what their 486169689Skan operands are. */ 487169689Skan return; 488169689Skan 489169689Skan default: 490169689Skan break; 491169689Skan } 492169689Skan /* Fall through. */ 493169689Skan 494169689Skan case tcc_comparison: /* a comparison expression */ 495169689Skan case tcc_unary: /* a unary arithmetic expression */ 496169689Skan case tcc_binary: /* a binary arithmetic expression */ 497169689Skan case tcc_reference: /* a reference */ 498169689Skan TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t); 499169689Skan for (i = 0; i < len; ++i) 500169689Skan { 501169689Skan tree op = TREE_OPERAND (t, i); 502169689Skan if (op && TREE_SIDE_EFFECTS (op)) 503169689Skan TREE_SIDE_EFFECTS (t) = 1; 504169689Skan } 505169689Skan break; 506169689Skan 507169689Skan default: 508169689Skan /* Can never be used with non-expressions. */ 509169689Skan gcc_unreachable (); 510169689Skan } 511169689Skan} 512