gcc/tree-gimple.c

   1 /* Functions to analyze and validate GIMPLE trees.
   2    Copyright (C) 2002, 2003 Free Software Foundation, Inc.
   3    Contributed by Diego Novillo <dnovillo@redhat.com>
   4    Rewritten by Jason Merrill <jason@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 2, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to
  20 the Free Software Foundation, 59 Temple Place - Suite 330,
  21 Boston, MA 02111-1307, 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 "output.h"
  31 #include "rtl.h"
  32 #include "expr.h"
  33 #include "bitmap.h"
  34
  35 /* GCC GIMPLE structure
  36
  37    Inspired by the SIMPLE C grammar at
  38
  39         http://www-acaps.cs.mcgill.ca/info/McCAT/McCAT.html
  40
  41    function:
  42      FUNCTION_DECL
  43        DECL_SAVED_TREE -> block
  44    block:
  45      BIND_EXPR
  46        BIND_EXPR_VARS -> DECL chain
  47        BIND_EXPR_BLOCK -> BLOCK
  48        BIND_EXPR_BODY -> compound-stmt
  49    compound-stmt:
  50      COMPOUND_EXPR
  51        op0 -> non-compound-stmt
  52        op1 -> stmt
  53      | EXPR_VEC
  54        (or other alternate solution)
  55    stmt: compound-stmt | non-compound-stmt
  56    non-compound-stmt:
  57      block
  58      | if-stmt
  59      | switch-stmt
  60      | jump-stmt
  61      | label-stmt
  62      | try-stmt
  63      | modify-stmt
  64      | call-stmt
  65    if-stmt:
  66      COND_EXPR
  67        op0 -> condition
  68        op1 -> stmt
  69        op2 -> stmt
  70    switch-stmt:
  71      SWITCH_EXPR
  72        op0 -> val
  73        op1 -> stmt
  74        op2 -> array of case labels (as LABEL_DECLs?)
  75          FIXME: add case value info
  76         The SWITCH_LABELS (op2) are sorted in ascending order, and the
  77         last label in the vector is always the default case.
  78    jump-stmt:
  79        GOTO_EXPR
  80          op0 -> LABEL_DECL | '*' ID
  81      | RETURN_EXPR
  82          op0 -> NULL_TREE
  83               | RESULT_DECL
  84               | MODIFY_EXPR -> RESULT_DECL, varname
  85      | THROW_EXPR?  do we need/want such a thing for opts, perhaps
  86          to generate an ERT_THROW region?  I think so.
  87          Hmm...this would only work at the GIMPLE level, where we know that
  88            the call args don't have any EH impact.  Perhaps
  89            annotation of the CALL_EXPR would work better.
  90      | RESX_EXPR
  91    label-stmt:
  92      LABEL_EXPR
  93          op0 -> LABEL_DECL
  94      | CASE_LABEL_EXPR
  95          CASE_LOW -> val | NULL_TREE
  96          CASE_HIGH -> val | NULL_TREE
  97          CASE_LABEL -> LABEL_DECL  FIXME
  98    try-stmt:
  99      TRY_CATCH_EXPR
 100        op0 -> stmt
 101        op1 -> handler
 102      | TRY_FINALLY_EXPR
 103        op0 -> stmt
 104        op1 -> stmt
 105    handler:
 106      catch-seq
 107      | EH_FILTER_EXPR
 108      | stmt
 109    modify-stmt:
 110      MODIFY_EXPR
 111        op0 -> lhs
 112        op1 -> rhs
 113    call-stmt: CALL_EXPR
 114      op0 -> ID | '&' ID
 115      op1 -> arglist
 116
 117    addr-expr-arg : compref | ID
 118    lhs: addr-expr-arg | '*' ID | bitfieldref
 119    min-lval: ID | '*' ID
 120    bitfieldref :
 121      BIT_FIELD_REF
 122        op0 -> inner_compref
 123        op1 -> CONST
 124        op2 -> var
 125    compref :
 126      COMPONENT_REF
 127        op0 -> inner_compref
 128      | ARRAY_REF
 129        op0 -> inner_compref
 130        op1 -> val
 131        op2 -> val
 132        op3 -> val
 133      | ARRAY_RANGE_REF
 134        op0 -> inner_compref
 135        op1 -> val
 136        op2 -> val
 137        op3 -> val
 138      | REALPART_EXPR
 139        op0 -> inner_compref
 140      | IMAGPART_EXPR
 141        op0 -> inner_compref
 142
 143    inner_compref : compref | min_lval
 144      | VIEW_CONVERT_EXPR
 145        op0 -> inner_compref
 146      | NOP_EXPR
 147        op0 -> inner_compref
 148      | CONVERT_EXPR
 149        op0 -> inner_compref
 150
 151    condition : val | val relop val
 152    val : ID | CONST
 153
 154    rhs        : varname | CONST
 155               | '*' ID
 156               | '&' addr-expr-arg
 157               | call_expr
 158               | unop val
 159               | val binop val
 160               | '(' cast ')' val
 161
 162               (cast here stands for all valid C typecasts)
 163
 164       unop
 165               : '+'
 166               | '-'
 167               | '!'
 168               | '~'
 169
 170       binop
 171               : relop | '-'
 172               | '+'
 173               | '/'
 174               | '*'
 175               | '%'
 176               | '&'
 177               | '|'
 178               | '<<'
 179               | '>>'
 180               | '^'
 181
 182       relop
 183               : '<'
 184               | '<='
 185               | '>'
 186               | '>='
 187               | '=='
 188               | '!='
 189
 190 */
 191
 192 static inline bool is_gimple_id (tree);
 193
 194 /* Validation of GIMPLE expressions.  */
 195
 196 /* Return nonzero if T is a GIMPLE RHS:
 197
 198       rhs     : varname | CONST
 199               | '*' ID
 200               | '&' varname_or_temp
 201               | call_expr
 202               | unop val
 203               | val binop val
 204               | '(' cast ')' val
 205               | <CONSTRUCTOR <gimple_val ...>>
 206
 207    The last option is only valid GIMPLE for vector and complex types;
 208    aggregate types should have their constructors decomposed.  */
 209
 210 bool
 211 is_gimple_rhs (tree t)
 212 {
 213   enum tree_code code = TREE_CODE (t);
 214
 215   switch (TREE_CODE_CLASS (code))
 216     {
 217     case '1':
 218     case '2':
 219     case '<':
 220       return 1;
 221
 222     default:
 223       break;
 224     }
 225
 226   switch (code)
 227     {
 228     case TRUTH_NOT_EXPR:
 229     case TRUTH_AND_EXPR:
 230     case TRUTH_OR_EXPR:
 231     case TRUTH_XOR_EXPR:
 232     case ADDR_EXPR:
 233     case CALL_EXPR:
 234     case CONSTRUCTOR:
 235     case COMPLEX_EXPR:
 236       /* FIXME lower VA_ARG_EXPR.  */
 237     case VA_ARG_EXPR:
 238     case INTEGER_CST:
 239     case REAL_CST:
 240     case STRING_CST:
 241     case COMPLEX_CST:
 242     case VECTOR_CST:
 243       return 1;
 244
 245     default:
 246       break;
 247     }
 248
 249   if (is_gimple_lvalue (t) || is_gimple_val (t))
 250     return 1;
 251
 252   return 0;
 253 }
 254
 255 /* Returns nonzero if T is a valid CONSTRUCTOR component in GIMPLE, either
 256    a val or another CONSTRUCTOR.  */
 257
 258 bool
 259 is_gimple_constructor_elt (tree t)
 260 {
 261   return (is_gimple_val (t)
 262           || TREE_CODE (t) == CONSTRUCTOR);
 263 }
 264
 265 /*  Return nonzero if T is a valid LHS for a GIMPLE assignment expression.  */
 266
 267 bool
 268 is_gimple_lvalue (tree t)
 269 {
 270   return (is_gimple_addr_expr_arg (t)
 271           || TREE_CODE (t) == INDIRECT_REF
 272           /* These are complex lvalues, but don't have addresses, so they
 273              go here.  */
 274           || TREE_CODE (t) == BIT_FIELD_REF);
 275 }
 276
 277
 278 /*  Return nonzero if T is a GIMPLE condition:
 279
 280       condexpr
 281               : val
 282               | val relop val  */
 283
 284 bool
 285 is_gimple_condexpr (tree t)
 286 {
 287   return (is_gimple_val (t)
 288           || TREE_CODE_CLASS (TREE_CODE (t)) == '<');
 289 }
 290
 291
 292 /*  Return nonzero if T is a valid operand for '&':
 293
 294       varname
 295               : arrayref
 296               | compref
 297               | ID     */
 298
 299 bool
 300 is_gimple_addr_expr_arg (tree t)
 301 {
 302   return (is_gimple_id (t)
 303           || TREE_CODE (t) == ARRAY_REF
 304           || TREE_CODE (t) == ARRAY_RANGE_REF
 305           || TREE_CODE (t) == COMPONENT_REF
 306           || TREE_CODE (t) == REALPART_EXPR
 307           || TREE_CODE (t) == IMAGPART_EXPR
 308           || TREE_CODE (t) == INDIRECT_REF);
 309 }
 310
 311 /* Return nonzero if T is function invariant.  Or rather a restricted
 312    form of function invariant.  */
 313
 314 bool
 315 is_gimple_min_invariant (tree t)
 316 {
 317   switch (TREE_CODE (t))
 318     {
 319     case ADDR_EXPR:
 320       return TREE_INVARIANT (t);
 321
 322     case INTEGER_CST:
 323     case REAL_CST:
 324     case STRING_CST:
 325     case COMPLEX_CST:
 326     case VECTOR_CST:
 327       return !TREE_OVERFLOW (t);
 328
 329     default:
 330       return false;
 331     }
 332 }
 333
 334 /* Return nonzero if T looks like a valid GIMPLE statement.  */
 335
 336 bool
 337 is_gimple_stmt (tree t)
 338 {
 339   enum tree_code code = TREE_CODE (t);
 340
 341   if (IS_EMPTY_STMT (t))
 342     return 1;
 343
 344   switch (code)
 345     {
 346     case BIND_EXPR:
 347     case COND_EXPR:
 348       /* These are only valid if they're void.  */
 349       return VOID_TYPE_P (TREE_TYPE (t));
 350
 351     case SWITCH_EXPR:
 352     case GOTO_EXPR:
 353     case RETURN_EXPR:
 354     case LABEL_EXPR:
 355     case CASE_LABEL_EXPR:
 356     case TRY_CATCH_EXPR:
 357     case TRY_FINALLY_EXPR:
 358     case EH_FILTER_EXPR:
 359     case CATCH_EXPR:
 360     case ASM_EXPR:
 361     case RESX_EXPR:
 362     case PHI_NODE:
 363     case STATEMENT_LIST:
 364       /* These are always void.  */
 365       return 1;
 366
 367     case VA_ARG_EXPR:
 368       /* FIXME this should be lowered.  */
 369       return 1;
 370
 371     case COMPOUND_EXPR:
 372       /* FIXME should we work harder to make COMPOUND_EXPRs void?  */
 373     case CALL_EXPR:
 374     case MODIFY_EXPR:
 375       /* These are valid regardless of their type.  */
 376       return 1;
 377
 378     default:
 379       return 0;
 380     }
 381 }
 382
 383 /* Return nonzero if T is a variable.  */
 384
 385 bool
 386 is_gimple_variable (tree t)
 387 {
 388   return (TREE_CODE (t) == VAR_DECL
 389           || TREE_CODE (t) == PARM_DECL
 390           || TREE_CODE (t) == RESULT_DECL
 391           || TREE_CODE (t) == SSA_NAME);
 392 }
 393
 394 /*  Return nonzero if T is a GIMPLE identifier (something with an address).  */
 395
 396 static inline bool
 397 is_gimple_id (tree t)
 398 {
 399   return (is_gimple_variable (t)
 400           || TREE_CODE (t) == FUNCTION_DECL
 401           || TREE_CODE (t) == LABEL_DECL
 402           /* Allow string constants, since they are addressable.  */
 403           || TREE_CODE (t) == STRING_CST);
 404 }
 405
 406 /* Return nonzero if TYPE is a suitable type for a scalar register
 407    variable.  */
 408
 409 bool
 410 is_gimple_reg_type (tree type)
 411 {
 412   return (!AGGREGATE_TYPE_P (type)
 413           && TREE_CODE (type) != COMPLEX_TYPE);
 414 }
 415
 416
 417 /* Return nonzero if T is a scalar register variable.  */
 418
 419 bool
 420 is_gimple_reg (tree t)
 421 {
 422   if (TREE_CODE (t) == SSA_NAME)
 423     t = SSA_NAME_VAR (t);
 424
 425   return (is_gimple_variable (t)
 426           && is_gimple_reg_type (TREE_TYPE (t))
 427           /* A volatile decl is not acceptable because we can't reuse it as
 428              needed.  We need to copy it into a temp first.  */
 429           && ! TREE_THIS_VOLATILE (t)
 430           && ! TREE_ADDRESSABLE (t)
 431           && ! needs_to_live_in_memory (t));
 432 }
 433
 434 /* Return nonzero if T is a GIMPLE variable whose address is not needed.  */
 435
 436 bool
 437 is_gimple_non_addressable (tree t)
 438 {
 439   if (TREE_CODE (t) == SSA_NAME)
 440     t = SSA_NAME_VAR (t);
 441
 442   return (is_gimple_variable (t)
 443           && ! TREE_ADDRESSABLE (t)
 444           && ! needs_to_live_in_memory (t));
 445 }
 446
 447 /*  Return nonzero if T is a GIMPLE rvalue, i.e. an identifier or a
 448     constant.  */
 449
 450 bool
 451 is_gimple_val (tree t)
 452 {
 453   /* Make loads from volatiles and memory vars explicit.  */
 454   if (is_gimple_variable (t)
 455       && is_gimple_reg_type (TREE_TYPE (t))
 456       && !is_gimple_reg (t))
 457     return 0;
 458
 459   /* FIXME make these decls.  That can happen only when we expose the
 460      entire landing-pad construct at the tree level.  */
 461   if (TREE_CODE (t) == EXC_PTR_EXPR || TREE_CODE (t) == FILTER_EXPR)
 462     return 1;
 463
 464   return (is_gimple_variable (t) || is_gimple_min_invariant (t));
 465 }
 466
 467
 468 /*  Return true if T is a GIMPLE minimal lvalue, of the form
 469
 470     min_lval: ID | '(' '*' ID ')'
 471
 472     This never actually appears in the original SIMPLE grammar, but is
 473     repeated in several places.  */
 474
 475 bool
 476 is_gimple_min_lval (tree t)
 477 {
 478   return (is_gimple_id (t)
 479           || TREE_CODE (t) == INDIRECT_REF);
 480 }
 481
 482 /*  Return nonzero if T is a typecast operation of the form
 483     '(' cast ')' val.  */
 484
 485 bool
 486 is_gimple_cast (tree t)
 487 {
 488   return (TREE_CODE (t) == NOP_EXPR
 489           || TREE_CODE (t) == CONVERT_EXPR
 490           || TREE_CODE (t) == FIX_TRUNC_EXPR
 491           || TREE_CODE (t) == FIX_CEIL_EXPR
 492           || TREE_CODE (t) == FIX_FLOOR_EXPR
 493           || TREE_CODE (t) == FIX_ROUND_EXPR);
 494 }
 495
 496
 497 /* If T makes a function call, return the corresponding CALL_EXPR operand.
 498    Otherwise, return NULL_TREE.  */
 499
 500 tree
 501 get_call_expr_in (tree t)
 502 {
 503   if (TREE_CODE (t) == CALL_EXPR)
 504     return t;
 505   else if (TREE_CODE (t) == MODIFY_EXPR
 506            && TREE_CODE (TREE_OPERAND (t, 1)) == CALL_EXPR)
 507     return TREE_OPERAND (t, 1);
 508   else if (TREE_CODE (t) == RETURN_EXPR
 509            && TREE_OPERAND (t, 0)
 510            && TREE_CODE (TREE_OPERAND (t, 0)) == MODIFY_EXPR
 511            && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 1)) == CALL_EXPR)
 512     return TREE_OPERAND (TREE_OPERAND (t, 0), 1);
 513
 514   return NULL_TREE;
 515 }
 516
 517
 518 /* Given an _EXPR TOP, reorganize all of the nested _EXPRs with the same
 519    code so that they only appear as the second operand.  This should only
 520    be used for tree codes which are truly associative, such as
 521    COMPOUND_EXPR and TRUTH_ANDIF_EXPR.  Arithmetic is not associative
 522    enough, due to the limited precision of arithmetic data types.
 523
 524    This transformation is conservative; the operand 0 of a matching tree
 525    node will only change if it is also a matching node.  */
 526
 527 tree
 528 right_assocify_expr (tree top)
 529 {
 530   tree *p = &top;
 531   enum tree_code code = TREE_CODE (*p);
 532   while (TREE_CODE (*p) == code)
 533     {
 534       tree cur = *p;
 535       tree lhs = TREE_OPERAND (cur, 0);
 536       if (TREE_CODE (lhs) == code)
 537         {
 538           /* There's a left-recursion.  If we have ((a, (b, c)), d), we
 539              want to rearrange to (a, (b, (c, d))).  */
 540           tree *q;
 541
 542           /* Replace cur with the lhs; move (a, *) up.  */
 543           *p = lhs;
 544
 545           if (code == COMPOUND_EXPR)
 546             {
 547               /* We need to give (b, c) the type of c; previously lhs had
 548                  the type of b.  */
 549               TREE_TYPE (lhs) = TREE_TYPE (cur);
 550               if (TREE_SIDE_EFFECTS (cur))
 551                 TREE_SIDE_EFFECTS (lhs) = 1;
 552             }
 553
 554           /* Walk through the op1 chain from there until we find something
 555              with a different code.  In this case, c.  */
 556           for (q = &TREE_OPERAND (lhs, 1); TREE_CODE (*q) == code;
 557                q = &TREE_OPERAND (*q, 1))
 558             TREE_TYPE (*q) = TREE_TYPE (cur);
 559
 560           /* Change (*, d) into (c, d).  */
 561           TREE_OPERAND (cur, 0) = *q;
 562
 563           /* And plug it in where c used to be.  */
 564           *q = cur;
 565         }
 566       else
 567         p = &TREE_OPERAND (cur, 1);
 568     }
 569   return top;
 570 }
 571
 572 /* Normalize the statement TOP.  If it is a COMPOUND_EXPR, reorganize it so
 573    that we can traverse it without recursion.  If it is null, replace it
 574    with a nop.  */
 575
 576 tree
 577 rationalize_compound_expr (tree top)
 578 {
 579   if (top == NULL_TREE)
 580     top = build_empty_stmt ();
 581   else if (TREE_CODE (top) == COMPOUND_EXPR)
 582     top = right_assocify_expr (top);
 583
 584   return top;
 585 }
 586
 587 /* Given a memory reference expression, return the base address.  Note that,
 588    in contrast with get_base_var, this will not recurse inside INDIRECT_REF
 589    expressions.  Therefore, given the reference PTR->FIELD, this function
 590    will return *PTR.  Whereas get_base_var would've returned PTR.  */
 591
 592 tree
 593 get_base_address (tree t)
 594 {
 595   do
 596     {
 597       if (SSA_VAR_P (t)
 598           || TREE_CODE (t) == STRING_CST
 599           || TREE_CODE (t) == CONSTRUCTOR
 600           || TREE_CODE (t) == INDIRECT_REF)
 601         return t;
 602
 603       if (TREE_CODE (t) == REALPART_EXPR || TREE_CODE (t) == IMAGPART_EXPR)
 604         t = TREE_OPERAND (t, 0);
 605       else if (handled_component_p (t))
 606         t = get_base_address (TREE_OPERAND (t, 0));
 607       else
 608         return NULL_TREE;
 609     }
 610   while (t);
 611
 612   return t;
 613 }
 614
 615
 616 void
 617 recalculate_side_effects (tree t)
 618 {
 619   enum tree_code code = TREE_CODE (t);
 620   int fro = first_rtl_op (code);
 621   int i;
 622
 623   switch (TREE_CODE_CLASS (code))
 624     {
 625     case 'e':
 626       switch (code)
 627         {
 628         case INIT_EXPR:
 629         case MODIFY_EXPR:
 630         case VA_ARG_EXPR:
 631         case RTL_EXPR:
 632         case PREDECREMENT_EXPR:
 633         case PREINCREMENT_EXPR:
 634         case POSTDECREMENT_EXPR:
 635         case POSTINCREMENT_EXPR:
 636           /* All of these have side-effects, no matter what their
 637              operands are.  */
 638           return;
 639
 640         default:
 641           break;
 642         }
 643       /* Fall through.  */
 644
 645     case '<':  /* a comparison expression */
 646     case '1':  /* a unary arithmetic expression */
 647     case '2':  /* a binary arithmetic expression */
 648     case 'r':  /* a reference */
 649       TREE_SIDE_EFFECTS (t) = TREE_THIS_VOLATILE (t);
 650       for (i = 0; i < fro; ++i)
 651         {
 652           tree op = TREE_OPERAND (t, i);
 653           if (op && TREE_SIDE_EFFECTS (op))
 654             TREE_SIDE_EFFECTS (t) = 1;
 655         }
 656       break;
 657    }
 658 }