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                                 && !tree_could_trap_p (t)
 160                                 && is_gimple_val (TREE_OPERAND (t, 0))
 161                                 && is_gimple_val (TREE_OPERAND (t, 1))));
 162 }
 163
 164 /*  Return true if T is something whose address can be taken.  */
 165
 166 bool
 167 is_gimple_addressable (tree t)
 168 {
 169   return (is_gimple_id (t) || handled_component_p (t)
 170           || INDIRECT_REF_P (t));
 171 }
 172
 173 /* Return true if T is a valid gimple constant.  */
 174
 175 bool
 176 is_gimple_constant (const_tree t)
 177 {
 178   switch (TREE_CODE (t))
 179     {
 180     case INTEGER_CST:
 181     case REAL_CST:
 182     case FIXED_CST:
 183     case STRING_CST:
 184     case COMPLEX_CST:
 185     case VECTOR_CST:
 186       return true;
 187
 188     /* Vector constant constructors are gimple invariant.  */
 189     case CONSTRUCTOR:
 190       if (TREE_TYPE (t) && TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 191         return TREE_CONSTANT (t);
 192       else
 193         return false;
 194
 195     default:
 196       return false;
 197     }
 198 }
 199
 200 /* Return true if T is a gimple address.  */
 201
 202 bool
 203 is_gimple_address (const_tree t)
 204 {
 205   tree op;
 206
 207   if (TREE_CODE (t) != ADDR_EXPR)
 208     return false;
 209
 210   op = TREE_OPERAND (t, 0);
 211   while (handled_component_p (op))
 212     {
 213       if ((TREE_CODE (op) == ARRAY_REF
 214            || TREE_CODE (op) == ARRAY_RANGE_REF)
 215           && !is_gimple_val (TREE_OPERAND (op, 1)))
 216             return false;
 217
 218       op = TREE_OPERAND (op, 0);
 219     }
 220
 221   if (CONSTANT_CLASS_P (op) || INDIRECT_REF_P (op))
 222     return true;
 223
 224   switch (TREE_CODE (op))
 225     {
 226     case PARM_DECL:
 227     case RESULT_DECL:
 228     case LABEL_DECL:
 229     case FUNCTION_DECL:
 230     case VAR_DECL:
 231     case CONST_DECL:
 232       return true;
 233
 234     default:
 235       return false;
 236     }
 237 }
 238
 239 /* Return true if T is a gimple invariant address.  */
 240
 241 bool
 242 is_gimple_invariant_address (const_tree t)
 243 {
 244   tree op;
 245
 246   if (TREE_CODE (t) != ADDR_EXPR)
 247     return false;
 248
 249   op = TREE_OPERAND (t, 0);
 250   while (handled_component_p (op))
 251     {
 252       switch (TREE_CODE (op))
 253         {
 254         case ARRAY_REF:
 255         case ARRAY_RANGE_REF:
 256           if (!is_gimple_constant (TREE_OPERAND (op, 1))
 257               || TREE_OPERAND (op, 2) != NULL_TREE
 258               || TREE_OPERAND (op, 3) != NULL_TREE)
 259             return false;
 260           break;
 261
 262         case COMPONENT_REF:
 263           if (TREE_OPERAND (op, 2) != NULL_TREE)
 264             return false;
 265           break;
 266
 267         default:;
 268         }
 269       op = TREE_OPERAND (op, 0);
 270     }
 271
 272   return CONSTANT_CLASS_P (op) || decl_address_invariant_p (op);
 273 }
 274
 275 /* Return true if T is a GIMPLE minimal invariant.  It's a restricted
 276    form of function invariant.  */
 277
 278 bool
 279 is_gimple_min_invariant (const_tree t)
 280 {
 281   if (TREE_CODE (t) == ADDR_EXPR)
 282     return is_gimple_invariant_address (t);
 283
 284   return is_gimple_constant (t);
 285 }
 286
 287 /* Return true if T looks like a valid GIMPLE statement.  */
 288
 289 bool
 290 is_gimple_stmt (tree t)
 291 {
 292   const enum tree_code code = TREE_CODE (t);
 293
 294   switch (code)
 295     {
 296     case NOP_EXPR:
 297       /* The only valid NOP_EXPR is the empty statement.  */
 298       return IS_EMPTY_STMT (t);
 299
 300     case BIND_EXPR:
 301     case COND_EXPR:
 302       /* These are only valid if they're void.  */
 303       return TREE_TYPE (t) == NULL || VOID_TYPE_P (TREE_TYPE (t));
 304
 305     case SWITCH_EXPR:
 306     case GOTO_EXPR:
 307     case RETURN_EXPR:
 308     case LABEL_EXPR:
 309     case CASE_LABEL_EXPR:
 310     case TRY_CATCH_EXPR:
 311     case TRY_FINALLY_EXPR:
 312     case EH_FILTER_EXPR:
 313     case CATCH_EXPR:
 314     case CHANGE_DYNAMIC_TYPE_EXPR:
 315     case ASM_EXPR:
 316     case RESX_EXPR:
 317     case PHI_NODE:
 318     case STATEMENT_LIST:
 319     case OMP_PARALLEL:
 320     case OMP_FOR:
 321     case OMP_SECTIONS:
 322     case OMP_SECTIONS_SWITCH:
 323     case OMP_SECTION:
 324     case OMP_SINGLE:
 325     case OMP_MASTER:
 326     case OMP_ORDERED:
 327     case OMP_CRITICAL:
 328     case OMP_RETURN:
 329     case OMP_CONTINUE:
 330     case OMP_ATOMIC_LOAD:
 331     case OMP_ATOMIC_STORE:
 332       /* These are always void.  */
 333       return true;
 334
 335     case CALL_EXPR:
 336     case GIMPLE_MODIFY_STMT:
 337     case PREDICT_EXPR:
 338       /* These are valid regardless of their type.  */
 339       return true;
 340
 341     default:
 342       return false;
 343     }
 344 }
 345
 346 /* Return true if T is a variable.  */
 347
 348 bool
 349 is_gimple_variable (tree t)
 350 {
 351   return (TREE_CODE (t) == VAR_DECL
 352           || TREE_CODE (t) == PARM_DECL
 353           || TREE_CODE (t) == RESULT_DECL
 354           || TREE_CODE (t) == SSA_NAME);
 355 }
 356
 357 /*  Return true if T is a GIMPLE identifier (something with an address).  */
 358
 359 bool
 360 is_gimple_id (tree t)
 361 {
 362   return (is_gimple_variable (t)
 363           || TREE_CODE (t) == FUNCTION_DECL
 364           || TREE_CODE (t) == LABEL_DECL
 365           || TREE_CODE (t) == CONST_DECL
 366           /* Allow string constants, since they are addressable.  */
 367           || TREE_CODE (t) == STRING_CST);
 368 }
 369
 370 /* Return true if TYPE is a suitable type for a scalar register variable.  */
 371
 372 bool
 373 is_gimple_reg_type (tree type)
 374 {
 375   /* In addition to aggregate types, we also exclude complex types if not
 376      optimizing because they can be subject to partial stores in GNU C by
 377      means of the __real__ and __imag__ operators and we cannot promote
 378      them to total stores (see gimplify_modify_expr_complex_part).  */
 379   return !(AGGREGATE_TYPE_P (type)
 380            || (TREE_CODE (type) == COMPLEX_TYPE && !optimize));
 381
 382 }
 383
 384 /* Return true if T is a non-aggregate register variable.  */
 385
 386 bool
 387 is_gimple_reg (tree t)
 388 {
 389   if (TREE_CODE (t) == SSA_NAME)
 390     t = SSA_NAME_VAR (t);
 391
 392   if (MTAG_P (t))
 393     return false;
 394
 395   if (!is_gimple_variable (t))
 396     return false;
 397
 398   if (!is_gimple_reg_type (TREE_TYPE (t)))
 399     return false;
 400
 401   /* A volatile decl is not acceptable because we can't reuse it as
 402      needed.  We need to copy it into a temp first.  */
 403   if (TREE_THIS_VOLATILE (t))
 404     return false;
 405
 406   /* We define "registers" as things that can be renamed as needed,
 407      which with our infrastructure does not apply to memory.  */
 408   if (needs_to_live_in_memory (t))
 409     return false;
 410
 411   /* Hard register variables are an interesting case.  For those that
 412      are call-clobbered, we don't know where all the calls are, since
 413      we don't (want to) take into account which operations will turn
 414      into libcalls at the rtl level.  For those that are call-saved,
 415      we don't currently model the fact that calls may in fact change
 416      global hard registers, nor do we examine ASM_CLOBBERS at the tree
 417      level, and so miss variable changes that might imply.  All around,
 418      it seems safest to not do too much optimization with these at the
 419      tree level at all.  We'll have to rely on the rtl optimizers to
 420      clean this up, as there we've got all the appropriate bits exposed.  */
 421   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 422     return false;
 423
 424   /* Complex and vector values must have been put into SSA-like form.
 425      That is, no assignments to the individual components.  */
 426   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
 427       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
 428     return DECL_GIMPLE_REG_P (t);
 429
 430   return true;
 431 }
 432
 433
 434 /* Returns true if T is a GIMPLE formal temporary variable.  */
 435
 436 bool
 437 is_gimple_formal_tmp_var (tree t)
 438 {
 439   if (TREE_CODE (t) == SSA_NAME)
 440     return true;
 441
 442   return TREE_CODE (t) == VAR_DECL && DECL_GIMPLE_FORMAL_TEMP_P (t);
 443 }
 444
 445 /* Returns true if T is a GIMPLE formal temporary register variable.  */
 446
 447 bool
 448 is_gimple_formal_tmp_reg (tree t)
 449 {
 450   /* The intent of this is to get hold of a value that won't change.
 451      An SSA_NAME qualifies no matter if its of a user variable or not.  */
 452   if (TREE_CODE (t) == SSA_NAME)
 453     return true;
 454
 455   /* We don't know the lifetime characteristics of user variables.  */
 456   if (!is_gimple_formal_tmp_var (t))
 457     return false;
 458
 459   /* Finally, it must be capable of being placed in a register.  */
 460   return is_gimple_reg (t);
 461 }
 462
 463 /* Return true if T is a GIMPLE variable whose address is not needed.  */
 464
 465 bool
 466 is_gimple_non_addressable (tree t)
 467 {
 468   if (TREE_CODE (t) == SSA_NAME)
 469     t = SSA_NAME_VAR (t);
 470
 471   return (is_gimple_variable (t) && ! needs_to_live_in_memory (t));
 472 }
 473
 474 /* Return true if T is a GIMPLE rvalue, i.e. an identifier or a constant.  */
 475
 476 bool
 477 is_gimple_val (tree t)
 478 {
 479   /* Make loads from volatiles and memory vars explicit.  */
 480   if (is_gimple_variable (t)
 481       && is_gimple_reg_type (TREE_TYPE (t))
 482       && !is_gimple_reg (t))
 483     return false;
 484
 485   /* FIXME make these decls.  That can happen only when we expose the
 486      entire landing-pad construct at the tree level.  */
 487   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 488     return true;
 489
 490   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 491 }
 492
 493 /* Similarly, but accept hard registers as inputs to asm statements.  */
 494
 495 bool
 496 is_gimple_asm_val (tree t)
 497 {
 498   if (TREE_CODE (t) == VAR_DECL && DECL_HARD_REGISTER (t))
 499     return true;
 500
 501   return is_gimple_val (t);
 502 }
 503
 504 /* Return true if T is a GIMPLE minimal lvalue.  */
 505
 506 bool
 507 is_gimple_min_lval (tree t)
 508 {
 509   return (is_gimple_id (t)
 510           || TREE_CODE (t) == INDIRECT_REF);
 511 }
 512
 513 /* Return true if T is a typecast operation.  */
 514
 515 bool
 516 is_gimple_cast (tree t)
 517 {
 518   return (CONVERT_EXPR_P (t)
 519           || TREE_CODE (t) == FIX_TRUNC_EXPR);
 520 }
 521
 522 /* Return true if T is a valid function operand of a CALL_EXPR.  */
 523
 524 bool
 525 is_gimple_call_addr (tree t)
 526 {
 527   return (TREE_CODE (t) == OBJ_TYPE_REF
 528           || is_gimple_val (t));
 529 }
 530
 531 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 532    Otherwise, return NULL_TREE.  */
 533
 534 tree
 535 get_call_expr_in (tree t)
 536 {
 537   /* FIXME tuples: delete the assertion below when conversion complete.  */
 538   gcc_assert (TREE_CODE (t) != MODIFY_EXPR);
 539   if (TREE_CODE (t) == GIMPLE_MODIFY_STMT)
 540     t = GIMPLE_STMT_OPERAND (t, 1);
 541   if (TREE_CODE (t) == WITH_SIZE_EXPR)
 542     t = TREE_OPERAND (t, 0);
 543   if (TREE_CODE (t) == CALL_EXPR)
 544     return t;
 545   return NULL_TREE;
 546 }
 547
 548 /* Given a memory reference expression T, return its base address.
 549    The base address of a memory reference expression is the main
 550    object being referenced.  For instance, the base address for
 551    'array[i].fld[j]' is 'array'.  You can think of this as stripping
 552    away the offset part from a memory address.
 553
 554    This function calls handled_component_p to strip away all the inner
 555    parts of the memory reference until it reaches the base object.  */
 556
 557 tree
 558 get_base_address (tree t)
 559 {
 560   while (handled_component_p (t))
 561     t = TREE_OPERAND (t, 0);
 562
 563   if (SSA_VAR_P (t)
 564       || TREE_CODE (t) == STRING_CST
 565       || TREE_CODE (t) == CONSTRUCTOR
 566       || INDIRECT_REF_P (t))
 567     return t;
 568   else
 569     return NULL_TREE;
 570 }
 571
 572 void
 573 recalculate_side_effects (tree t)
 574 {
 575   enum tree_code code = TREE_CODE (t);
 576   int len = TREE_OPERAND_LENGTH (t);
 577   int i;
 578
 579   switch (TREE_CODE_CLASS (code))
 580     {
 581     case tcc_expression:
 582       switch (code)
 583         {
 584         case INIT_EXPR:
 585         case GIMPLE_MODIFY_STMT:
 586         case VA_ARG_EXPR:
 587         case PREDECREMENT_EXPR:
 588         case PREINCREMENT_EXPR:
 589         case POSTDECREMENT_EXPR:
 590         case POSTINCREMENT_EXPR:
 591           /* All of these have side-effects, no matter what their
 592              operands are.  */
 593           return;
 594
 595         default:
 596           break;
 597         }
 598       /* Fall through.  */
 599
 600     case tcc_comparison:  /* a comparison expression */
 601     case tcc_unary:       /* a unary arithmetic expression */
 602     case tcc_binary:      /* a binary arithmetic expression */
 603     case tcc_reference:   /* a reference */
 604     case tcc_vl_exp:        /* a function call */
 605       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 606       for (i = 0; i < len; ++i)
 607         {
 608           tree op = TREE_OPERAND (t, i);
 609           if (op && TREE_SIDE_EFFECTS (op))
 610             TREE_SIDE_EFFECTS (t) = 1;
 611         }
 612       break;
 613
 614     default:
 615       /* Can never be used with non-expressions.  */
 616       gcc_unreachable ();
 617    }
 618 }
 619
 620 /* Canonicalize a tree T for use in a COND_EXPR as conditional.  Returns
 621    a canonicalized tree that is valid for a COND_EXPR or NULL_TREE, if
 622    we failed to create one.  */
 623
 624 tree
 625 canonicalize_cond_expr_cond (tree t)
 626 {
 627   /* For (bool)x use x != 0.  */
 628   if (TREE_CODE (t) == NOP_EXPR
 629       && TREE_TYPE (t) == boolean_type_node)
 630     {
 631       tree top0 = TREE_OPERAND (t, 0);
 632       t = build2 (NE_EXPR, TREE_TYPE (t),
 633                   top0, build_int_cst (TREE_TYPE (top0), 0));
 634     }
 635   /* For !x use x == 0.  */
 636   else if (TREE_CODE (t) == TRUTH_NOT_EXPR)
 637     {
 638       tree top0 = TREE_OPERAND (t, 0);
 639       t = build2 (EQ_EXPR, TREE_TYPE (t),
 640                   top0, build_int_cst (TREE_TYPE (top0), 0));
 641     }
 642   /* For cmp ? 1 : 0 use cmp.  */
 643   else if (TREE_CODE (t) == COND_EXPR
 644            && COMPARISON_CLASS_P (TREE_OPERAND (t, 0))
 645            && integer_onep (TREE_OPERAND (t, 1))
 646            && integer_zerop (TREE_OPERAND (t, 2)))
 647     {
 648       tree top0 = TREE_OPERAND (t, 0);
 649       t = build2 (TREE_CODE (top0), TREE_TYPE (t),
 650                   TREE_OPERAND (top0, 0), TREE_OPERAND (top0, 1));
 651     }
 652
 653   if (is_gimple_condexpr (t))
 654     return t;
 655
 656   return NULL_TREE;
 657 }