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