gcc/tree-gimple.c

   1 /* Functions to analyze and validate GIMPLE trees.
   2    Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007
   3    Free Software Foundation, Inc.
   4    Contributed by Diego Novillo <dnovillo@redhat.com>
   5    Rewritten by Jason Merrill <jason@redhat.com>
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify
  10 it under the terms of the GNU General Public License as published by
  11 the Free Software Foundation; either version 3, or (at your option)
  12 any later version.
  13
  14 GCC is distributed in the hope that it will be useful,
  15 but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 GNU General Public License for more details.
  18
  19 You should have received a copy of the GNU General Public License
  20 along with GCC; see the file COPYING3.  If not see
  21 <http://www.gnu.org/licenses/>.  */
  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
  42 bool
  43 is_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 COND_EXPR:
  65     case ADDR_EXPR:
  66     case CALL_EXPR:
  67     case CONSTRUCTOR:
  68     case COMPLEX_EXPR:
  69     case INTEGER_CST:
  70     case REAL_CST:
  71     case FIXED_CST:
  72     case STRING_CST:
  73     case COMPLEX_CST:
  74     case VECTOR_CST:
  75     case OBJ_TYPE_REF:
  76     case ASSERT_EXPR:
  77       return true;
  78
  79     default:
  80       break;
  81     }
  82
  83   return is_gimple_lvalue (t) || is_gimple_val (t);
  84 }
  85
  86 /* Returns true iff T is a valid RHS for an assignment to a renamed
  87    user -- or front-end generated artificial -- variable.  */
  88
  89 bool
  90 is_gimple_reg_rhs (tree t)
  91 {
  92   /* If the RHS of the GIMPLE_MODIFY_STMT may throw or make a nonlocal goto
  93      and the LHS is a user variable, then we need to introduce a formal
  94      temporary.  This way the optimizers can determine that the user
  95      variable is only modified if evaluation of the RHS does not throw.
  96
  97      Don't force a temp of a non-renamable type; the copy could be
  98      arbitrarily expensive.  Instead we will generate a VDEF for
  99      the assignment.  */
 100
 101   if (is_gimple_reg_type (TREE_TYPE (t))
 102       && ((TREE_CODE (t) == CALL_EXPR && TREE_SIDE_EFFECTS (t))
 103           || tree_could_throw_p (t)))
 104     return false;
 105
 106   return is_gimple_formal_tmp_rhs (t);
 107 }
 108
 109 /* Returns true iff T is a valid RHS for an assignment to an un-renamed
 110    LHS, or for a call argument.  */
 111
 112 bool
 113 is_gimple_mem_rhs (tree t)
 114 {
 115   /* If we're dealing with a renamable type, either source or dest must be
 116      a renamed variable.  Also force a temporary if the type doesn't need
 117      to be stored in memory, since it's cheap and prevents erroneous
 118      tailcalls (PR 17526).  */
 119   if (is_gimple_reg_type (TREE_TYPE (t))
 120       || (TYPE_MODE (TREE_TYPE (t)) != BLKmode
 121           && (TREE_CODE (t) != CALL_EXPR
 122               || ! aggregate_value_p (t, t))))
 123     return is_gimple_val (t);
 124   else
 125     return is_gimple_formal_tmp_rhs (t);
 126 }
 127
 128 /* Returns the appropriate RHS predicate for this LHS.  */
 129
 130 gimple_predicate
 131 rhs_predicate_for (tree lhs)
 132 {
 133   if (is_gimple_formal_tmp_var (lhs))
 134     return is_gimple_formal_tmp_rhs;
 135   else if (is_gimple_reg (lhs))
 136     return is_gimple_reg_rhs;
 137   else
 138     return is_gimple_mem_rhs;
 139 }
 140
 141 /*  Return true if T is a valid LHS for a GIMPLE assignment expression.  */
 142
 143 bool
 144 is_gimple_lvalue (tree t)
 145 {
 146   return (is_gimple_addressable (t)
 147           || TREE_CODE (t) == WITH_SIZE_EXPR
 148           /* These are complex lvalues, but don't have addresses, so they
 149              go here.  */
 150           || TREE_CODE (t) == BIT_FIELD_REF);
 151 }
 152
 153 /*  Return true if T is a GIMPLE condition.  */
 154
 155 bool
 156 is_gimple_condexpr (tree t)
 157 {
 158   return (is_gimple_val (t) || COMPARISON_CLASS_P (t));
 159 }
 160
 161 /*  Return true if T is something whose address can be taken.  */
 162
 163 bool
 164 is_gimple_addressable (tree t)
 165 {
 166   return (is_gimple_id (t) || handled_component_p (t)
 167           || INDIRECT_REF_P (t));
 168 }
 169
 170 /* Return true if T is a valid gimple constant.  */
 171
 172 bool
 173 is_gimple_constant (const_tree t)
 174 {
 175   switch (TREE_CODE (t))
 176     {
 177     case INTEGER_CST:
 178     case REAL_CST:
 179     case FIXED_CST:
 180     case STRING_CST:
 181     case COMPLEX_CST:
 182     case VECTOR_CST:
 183       return true;
 184
 185     /* Vector constant constructors are gimple invariant.  */
 186     case CONSTRUCTOR:
 187       if (TREE_TYPE (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 188         return TREE_CONSTANT (t);
 189       else
 190         return false;
 191
 192     default:
 193       return false;
 194     }
 195 }
 196
 197 /* Return true if T is a gimple invariant address.  */
 198
 199 bool
 200 is_gimple_invariant_address (const_tree t)
 201 {
 202   tree op;
 203
 204   if (TREE_CODE (t) != ADDR_EXPR)
 205     return false;
 206
 207   op = TREE_OPERAND (t, 0);
 208   while (handled_component_p (op))
 209     {
 210       switch (TREE_CODE (op))
 211         {
 212         case ARRAY_REF:
 213         case ARRAY_RANGE_REF:
 214           if (!is_gimple_constant (TREE_OPERAND (op, 1))
 215               || TREE_OPERAND (op, 2) != NULL_TREE
 216               || TREE_OPERAND (op, 3) != NULL_TREE)
 217             return false;
 218           break;
 219
 220         case COMPONENT_REF:
 221           if (TREE_OPERAND (op, 2) != NULL_TREE)
 222             return false;
 223           break;
 224
 225         default:;
 226         }
 227       op = TREE_OPERAND (op, 0);
 228     }
 229
 230   if (CONSTANT_CLASS_P (op))
 231     return true;
 232
 233   if (INDIRECT_REF_P (op))
 234     return false;
 235
 236   switch (TREE_CODE (op))
 237     {
 238     case PARM_DECL:
 239     case RESULT_DECL:
 240     case LABEL_DECL:
 241     case FUNCTION_DECL:
 242       return true;
 243
 244     case VAR_DECL:
 245       if (((TREE_STATIC (op) || DECL_EXTERNAL (op))
 246            && ! DECL_DLLIMPORT_P (op))
 247           || DECL_THREAD_LOCAL_P (op)
 248           || DECL_CONTEXT (op) == current_function_decl
 249           || decl_function_context (op) == current_function_decl)
 250         return true;
 251       break;
 252
 253     case CONST_DECL:
 254       if ((TREE_STATIC (op) || DECL_EXTERNAL (op))
 255           || decl_function_context (op) == current_function_decl)
 256         return true;
 257       break;
 258
 259     default:
 260       gcc_unreachable ();
 261     }
 262
 263   return false;
 264 }
 265
 266 /* Return true if T is a GIMPLE minimal invariant.  It's a restricted
 267    form of function invariant.  */
 268
 269 bool
 270 is_gimple_min_invariant (const_tree t)
 271 {
 272   if (TREE_CODE (t) == ADDR_EXPR)
 273     return is_gimple_invariant_address (t);
 274
 275   return is_gimple_constant (t);
 276 }
 277
 278 /* Return true if T looks like a valid GIMPLE statement.  */
 279
 280 bool
 281 is_gimple_stmt (tree t)
 282 {
 283   const enum tree_code code = TREE_CODE (t);
 284
 285   switch (code)
 286     {
 287     case NOP_EXPR:
 288       /* The only valid NOP_EXPR is the empty statement.  */
 289       return IS_EMPTY_STMT (t);
 290
 291     case BIND_EXPR:
 292     case COND_EXPR:
 293       /* These are only valid if they're void.  */
 294       return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
 295
 296     case SWITCH_EXPR:
 297     case GOTO_EXPR:
 298     case RETURN_EXPR:
 299     case LABEL_EXPR:
 300     case CASE_LABEL_EXPR:
 301     case TRY_CATCH_EXPR:
 302     case TRY_FINALLY_EXPR:
 303     case EH_FILTER_EXPR:
 304     case CATCH_EXPR:
 305     case CHANGE_DYNAMIC_TYPE_EXPR:
 306     case ASM_EXPR:
 307     case RESX_EXPR:
 308     case PHI_NODE:
 309     case STATEMENT_LIST:
 310     case OMP_PARALLEL:
 311     case OMP_FOR:
 312     case OMP_SECTIONS:
 313     case OMP_SECTIONS_SWITCH:
 314     case OMP_SECTION:
 315     case OMP_SINGLE:
 316     case OMP_MASTER:
 317     case OMP_ORDERED:
 318     case OMP_CRITICAL:
 319     case OMP_RETURN:
 320     case OMP_CONTINUE:
 321     case OMP_ATOMIC_LOAD:
 322     case OMP_ATOMIC_STORE:
 323       /* These are always void.  */
 324       return true;
 325
 326     case CALL_EXPR:
 327     case GIMPLE_MODIFY_STMT:
 328       /* These are valid regardless of their type.  */
 329       return true;
 330
 331     default:
 332       return false;
 333     }
 334 }
 335
 336 /* Return true if T is a variable.  */
 337
 338 bool
 339 is_gimple_variable (tree t)
 340 {
 341   return (TREE_CODE (t) == VAR_DECL
 342           || TREE_CODE (t) == PARM_DECL
 343           || TREE_CODE (t) == RESULT_DECL
 344           || TREE_CODE (t) == SSA_NAME);
 345 }
 346
 347 /*  Return true if T is a GIMPLE identifier (something with an address).  */
 348
 349 bool
 350 is_gimple_id (tree t)
 351 {
 352   return (is_gimple_variable (t)
 353           || TREE_CODE (t) == FUNCTION_DECL
 354           || TREE_CODE (t) == LABEL_DECL
 355           || TREE_CODE (t) == CONST_DECL
 356           /* Allow string constants, since they are addressable.  */
 357           || TREE_CODE (t) == STRING_CST);
 358 }
 359
 360 /* Return true if TYPE is a suitable type for a scalar register variable.  */
 361
 362 bool
 363 is_gimple_reg_type (tree type)
 364 {
 365   /* In addition to aggregate types, we also exclude complex types if not
 366      optimizing because they can be subject to partial stores in GNU C by
 367      means of the __real__ and __imag__ operators and we cannot promote
 368      them to total stores (see gimplify_modify_expr_complex_part).  */
 369   return !(AGGREGATE_TYPE_P (type)
 370            || (TREE_CODE (type) == COMPLEX_TYPE && !optimize));
 371
 372 }
 373
 374 /* Return true if T is a non-aggregate register variable.  */
 375
 376 bool
 377 is_gimple_reg (tree t)
 378 {
 379   if (TREE_CODE (t) == SSA_NAME)
 380     t = SSA_NAME_VAR (t);
 381
 382   if (MTAG_P (t))
 383     return false;
 384
 385   if (!is_gimple_variable (t))
 386     return false;
 387
 388   if (!is_gimple_reg_type (TREE_TYPE (t)))
 389     return false;
 390
 391   /* A volatile decl is not acceptable because we can't reuse it as
 392      needed.  We need to copy it into a temp first.  */
 393   if (TREE_THIS_VOLATILE (t))
 394     return false;
 395
 396   /* We define "registers" as things that can be renamed as needed,
 397      which with our infrastructure does not apply to memory.  */
 398   if (needs_to_live_in_memory (t))
 399     return false;
 400
 401   /* Hard register variables are an interesting case.  For those that
 402      are call-clobbered, we don't know where all the calls are, since
 403      we don't (want to) take into account which operations will turn
 404      into libcalls at the rtl level.  For those that are call-saved,
 405      we don't currently model the fact that calls may in fact change
 406      global hard registers, nor do we examine ASM_CLOBBERS at the tree
 407      level, and so miss variable changes that might imply.  All around,
 408      it seems safest to not do too much optimization with these at the
 409      tree level at all.  We'll have to rely on the rtl optimizers to
 410      clean this up, as there we've got all the appropriate bits exposed.  */
 411   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 412     return false;
 413
 414   /* Complex and vector values must have been put into SSA-like form.
 415      That is, no assignments to the individual components.  */
 416   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
 417       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 418     return DECL_GIMPLE_REG_P (t);
 419
 420   return true;
 421 }
 422
 423
 424 /* Returns true if T is a GIMPLE formal temporary variable.  */
 425
 426 bool
 427 is_gimple_formal_tmp_var (tree t)
 428 {
 429   if (TREE_CODE (t) == SSA_NAME)
 430     return true;
 431
 432   return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t);
 433 }
 434
 435 /* Returns true if T is a GIMPLE formal temporary register variable.  */
 436
 437 bool
 438 is_gimple_formal_tmp_reg (tree t)
 439 {
 440   /* The intent of this is to get hold of a value that won't change.
 441      An SSA_NAME qualifies no matter if its of a user variable or not.  */
 442   if (TREE_CODE (t) == SSA_NAME)
 443     return true;
 444
 445   /* We don't know the lifetime characteristics of user variables.  */
 446   if (!is_gimple_formal_tmp_var (t))
 447     return false;
 448
 449   /* Finally, it must be capable of being placed in a register.  */
 450   return is_gimple_reg (t);
 451 }
 452
 453 /* Return true if T is a GIMPLE variable whose address is not needed.  */
 454
 455 bool
 456 is_gimple_non_addressable (tree t)
 457 {
 458   if (TREE_CODE (t) == SSA_NAME)
 459     t = SSA_NAME_VAR (t);
 460
 461   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
 462 }
 463
 464 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
 465
 466 bool
 467 is_gimple_val (tree t)
 468 {
 469   /* Make loads from volatiles and memory vars explicit.  */
 470   if (is_gimple_variable (t)
 471       && is_gimple_reg_type (TREE_TYPE (t))
 472       && !is_gimple_reg (t))
 473     return false;
 474
 475   /* FIXME make these decls.  That can happen only when we expose the
 476      entire landing-pad construct at the tree level.  */
 477   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 478     return true;
 479
 480   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 481 }
 482
 483 /* Similarly, but accept hard registers as inputs to asm statements.  */
 484
 485 bool
 486 is_gimple_asm_val (tree t)
 487 {
 488   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 489     return true;
 490
 491   return is_gimple_val (t);
 492 }
 493
 494 /* Return true if T is a GIMPLE minimal lvalue.  */
 495
 496 bool
 497 is_gimple_min_lval (tree t)
 498 {
 499   return (is_gimple_id (t)
 500           || TREE_CODE (t) == INDIRECT_REF);
 501 }
 502
 503 /* Return true if T is a typecast operation.  */
 504
 505 bool
 506 is_gimple_cast (tree t)
 507 {
 508   return (TREE_CODE (t) == NOP_EXPR
 509           || TREE_CODE (t) == CONVERT_EXPR
 510           || TREE_CODE (t) == FIX_TRUNC_EXPR);
 511 }
 512
 513 /* Return true if T is a valid function operand of a CALL_EXPR.  */
 514
 515 bool
 516 is_gimple_call_addr (tree t)
 517 {
 518   return (TREE_CODE (t) == OBJ_TYPE_REF
 519           || is_gimple_val (t));
 520 }
 521
 522 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 523    Otherwise, return NULL_TREE.  */
 524
 525 tree
 526 get_call_expr_in (tree t)
 527 {
 528   /* FIXME tuples: delete the assertion below when conversion complete.  */
 529   gcc_assert (TREE_CODE (t) != MODIFY_EXPR);
 530   if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
 531     t = GIMPLE_STMT_OPERAND (t, 1);
 532   if (TREE_CODE (t) == WITH_SIZE_EXPR)
 533     t = TREE_OPERAND (t, 0);
 534   if (TREE_CODE (t) == CALL_EXPR)
 535     return t;
 536   return NULL_TREE;
 537 }
 538
 539 /* Given a memory reference expression T, return its base address.
 540    The base address of a memory reference expression is the main
 541    object being referenced.  For instance, the base address for
 542    'array[i].fld[j]' is 'array'.  You can think of this as stripping
 543    away the offset part from a memory address.
 544
 545    This function calls handled_component_p to strip away all the inner
 546    parts of the memory reference until it reaches the base object.  */
 547
 548 tree
 549 get_base_address (tree t)
 550 {
 551   while (handled_component_p (t))
 552     t = TREE_OPERAND (t, 0);
 553
 554   if (SSA_VAR_P (t)
 555       || TREE_CODE (t) == STRING_CST
 556       || TREE_CODE (t) == CONSTRUCTOR
 557       || INDIRECT_REF_P (t))
 558     return t;
 559   else
 560     return NULL_TREE;
 561 }
 562
 563 void
 564 recalculate_side_effects (tree t)
 565 {
 566   enum tree_code code = TREE_CODE (t);
 567   int len = TREE_OPERAND_LENGTH (t);
 568   int i;
 569
 570   switch (TREE_CODE_CLASS (code))
 571     {
 572     case tcc_expression:
 573       switch (code)
 574         {
 575         case INIT_EXPR:
 576         case GIMPLE_MODIFY_STMT:
 577         case VA_ARG_EXPR:
 578         case PREDECREMENT_EXPR:
 579         case PREINCREMENT_EXPR:
 580         case POSTDECREMENT_EXPR:
 581         case POSTINCREMENT_EXPR:
 582           /* All of these have side-effects, no matter what their
 583              operands are.  */
 584           return;
 585
 586         default:
 587           break;
 588         }
 589       /* Fall through.  */
 590
 591     case tcc_comparison:  /* a comparison expression */
 592     case tcc_unary:       /* a unary arithmetic expression */
 593     case tcc_binary:      /* a binary arithmetic expression */
 594     case tcc_reference:   /* a reference */
 595     case tcc_vl_exp:        /* a function call */
 596       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 597       for (i = 0; i < len; ++i)
 598         {
 599           tree op = TREE_OPERAND (t, i);
 600           if (op && TREE_SIDE_EFFECTS (op))
 601             TREE_SIDE_EFFECTS (t) = 1;
 602         }
 603       break;
 604
 605     default:
 606       /* Can never be used with non-expressions.  */
 607       gcc_unreachable ();
 608    }
 609 }
 610
 611 /* Canonicalize a tree T for use in a COND_EXPR as conditional.  Returns
 612    a canonicalized tree that is valid for a COND_EXPR or NULL_TREE, if
 613    we failed to create one.  */
 614
 615 tree
 616 canonicalize_cond_expr_cond (tree t)
 617 {
 618   /* For (bool)x use x != 0.  */
 619   if (TREE_CODE (t) == NOP_EXPR
 620       && TREE_TYPE (t) == boolean_type_node)
 621     {
 622       tree top0 = TREE_OPERAND (t, 0);
 623       t = build2 (NE_EXPR, TREE_TYPE (t),
 624                   top0, build_int_cst (TREE_TYPE (top0), 0));
 625     }
 626   /* For !x use x == 0.  */
 627   else if (TREE_CODE (t) == TRUTH_NOT_EXPR)
 628     {
 629       tree top0 = TREE_OPERAND (t, 0);
 630       t = build2 (EQ_EXPR, TREE_TYPE (t),
 631                   top0, build_int_cst (TREE_TYPE (top0), 0));
 632     }
 633   /* For cmp ? 1 : 0 use cmp.  */
 634   else if (TREE_CODE (t) == COND_EXPR
 635            && COMPARISON_CLASS_P (TREE_OPERAND (t, 0))
 636            && integer_onep (TREE_OPERAND (t, 1))
 637            && integer_zerop (TREE_OPERAND (t, 2)))
 638     {
 639       tree top0 = TREE_OPERAND (t, 0);
 640       t = build2 (TREE_CODE (top0), TREE_TYPE (t),
 641                   TREE_OPERAND (top0, 0), TREE_OPERAND (top0, 1));
 642     }
 643
 644   /* A valid conditional for a COND_EXPR is either a gimple value
 645      or a comparison with two gimple value operands.  */
 646   if (is_gimple_val (t)
 647       || (COMPARISON_CLASS_P (t)
 648           && is_gimple_val (TREE_OPERAND (t, 0))
 649           && is_gimple_val (TREE_OPERAND (t, 1))))
 650     return t;
 651
 652   return NULL_TREE;
 653 }