gcc/tree-alias-common.c

   1 /* Tree based points-to analysis
   2    Copyright (C) 2002, 2003 Free Software Foundation, Inc.
   3    Contributed by Daniel Berlin <dberlin@dberlin.org>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2 of the License, or
  10 (at your option) any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; if not, write to the Free Software
  19 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20 */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "ggc.h"
  27 #include "tree-alias-type.h"
  28 #include "bitmap.h"
  29 #include "tree-alias-common.h"
  30
  31 /* If we have andersen's points-to analysis, include it.  */
  32 #ifdef HAVE_BANSHEE
  33 #include "tree-alias-ander.h"
  34 #endif
  35
  36 #include "flags.h"
  37 #include "rtl.h"
  38 #include "tm_p.h"
  39 #include "hard-reg-set.h"
  40 #include "basic-block.h"
  41 #include "output.h"
  42 #include "errors.h"
  43 #include "expr.h"
  44 #include "diagnostic.h"
  45 #include "tree.h"
  46 #include "c-common.h"
  47 #include "tree-flow.h"
  48 #include "tree-inline.h"
  49 #include "varray.h"
  50 #include "c-tree.h"
  51 #include "tree-gimple.h"
  52 #include "hashtab.h"
  53 #include "function.h"
  54 #include "cgraph.h"
  55 #include "tree-pass.h"
  56 #include "timevar.h"
  57
  58 /* Reduce ifdefery later.  */
  59 #ifndef HAVE_BANSHEE
  60 #define HAVE_BANSHEE 0
  61 #endif
  62
  63 /*  This file contains the implementation of the common parts of the
  64     tree points-to analysis infrastructure.
  65
  66     Overview:
  67
  68     This file contains the points-to analysis driver.  It does two main things:
  69     1. Keeps track of the PTA data for each variable (IE the data each
  70     specific PTA implementation wants to keep associated with a
  71     variable).
  72     2. Walks the function trees, calling the appropriate functions that
  73     each PTA implementation has implemented.
  74
  75     In order to speed up PTA queries, the PTA specific data is stored
  76     in the tree for *_DECL's, in DECL_PTA_ALIASVAR.  This way, we only
  77     need to use the hash table for non-DECL's.  */
  78 #define FIELD_BASED 0
  79
  80 /*  Array of all created alias_vars.
  81     Note that this should contain all the alias_vars we wanted
  82     marked during GC.  */
  83 static GTY((param_is (union alias_var_def))) varray_type alias_vars = NULL;
  84 struct tree_alias_ops *current_alias_ops;
  85
  86 /*  Array of local (to a function) alias_vars.
  87     Note that this should contain all the alias_vars that are
  88     local to this function.  We delete these from alias_vars before
  89     collection.  */
  90 static GTY(()) varray_type local_alias_vars;
  91 static GTY(()) varray_type local_alias_varnums;
  92 tree pta_global_var;
  93 static bitmap addrargs;
  94 static alias_var get_alias_var_decl (tree);
  95 static alias_var get_alias_var (tree);
  96 static void find_func_aliases (tree);
  97 static void deal_with_call_aliasing (tree, alias_var);
  98 static alias_var create_fun_alias_var_ptf (tree, tree);
  99 static alias_var create_fun_alias_var (tree, int);
 100 static alias_var create_alias_var (tree);
 101 static void intra_function_call (varray_type);
 102 static void get_values_from_constructor (tree, varray_type *, bitmap, int *);
 103 static bool call_may_clobber (tree);
 104 static bool call_may_return (tree);
 105
 106 /* Return true if a EXPR, which is a CALL_EXPR, may clobber variables.  */
 107
 108 static bool
 109 call_may_clobber (tree expr)
 110 {
 111   int flags;
 112
 113   if (TREE_CODE (expr) != CALL_EXPR)
 114     return false;
 115
 116   flags = call_expr_flags (expr);
 117   return (! (flags & (ECF_CONST | ECF_PURE | ECF_NORETURN)));
 118 }
 119
 120 /* Return true if a EXPR, which is a CALL_EXPR, may return.  */
 121
 122 static bool
 123 call_may_return (tree expr)
 124 {
 125   int flags;
 126
 127   if (TREE_CODE (expr) != CALL_EXPR)
 128     return false;
 129
 130   flags = call_expr_flags (expr);
 131   return ! (flags & ECF_NORETURN);
 132 }
 133
 134 /*  Get the alias_var for DECL.
 135     Creates the alias_var if it does not exist already. Also
 136     handles FUNCTION_DECL properly.  */
 137
 138 static alias_var
 139 get_alias_var_decl (tree decl)
 140 {
 141   alias_var newvar;
 142   if (TREE_CODE (decl) == FIELD_DECL)
 143     abort ();
 144   if (DECL_P (decl))
 145     {
 146       if (DECL_PTA_ALIASVAR (decl))
 147         return DECL_PTA_ALIASVAR (decl);
 148     }
 149
 150   if (TREE_CODE (decl) == FUNCTION_DECL)
 151     newvar = create_fun_alias_var  (decl, 0);
 152   else
 153     {
 154       newvar = create_alias_var (decl);
 155       /* Assign globals to global var for purposes of intraprocedural
 156          analysis.  */
 157       if (TREE_STATIC (decl) && decl != pta_global_var)
 158         {
 159           current_alias_ops->addr_assign (current_alias_ops,
 160                                           get_alias_var (pta_global_var),
 161                                           newvar);
 162           /* If the global has some DECL_INITIAL, we need to process
 163              it here.  */
 164           if (DECL_INITIAL (decl))
 165             find_func_aliases (decl);
 166         }
 167     }
 168
 169   if (!current_alias_ops->ip)
 170     {
 171       if (!current_alias_ops->ip_partial
 172           || (TREE_CODE (decl) != FUNCTION_DECL
 173               && TREE_CODE (decl) != PARM_DECL))
 174         {
 175           VARRAY_PUSH_INT (local_alias_varnums, ALIAS_VAR_VARNUM (newvar));
 176           VARRAY_PUSH_TREE (local_alias_vars, decl);
 177         }
 178     }
 179   return newvar;
 180 }
 181
 182 /* Get the alias_var for an expression EXPR.
 183    Note that this function expects to only be handed a RHS or LHS, not
 184    a MODIFY_EXPR.  */
 185
 186 static alias_var
 187 get_alias_var (tree expr)
 188 {
 189   /* If it's a decl, get the alias var of the decl. We farm this off
 190      to get_alias_var_decl so it can abort if the alias var doesn't
 191      exist, and in case something else *knows* it has a decl, and
 192      wants the alias var.  */
 193
 194   if (DECL_P (expr))
 195     return get_alias_var_decl (expr);
 196
 197   /* True constants have no aliases (unless modifiable strings are on,
 198      in which case i don't think we'll end up with a STRING_CST anyway) */
 199   if (TREE_CODE_CLASS (TREE_CODE (expr)) == 'c')
 200     return NULL;
 201
 202
 203   switch (TREE_CODE (expr))
 204     {
 205     case ARRAY_REF:
 206     case ARRAY_RANGE_REF:
 207       {
 208         /* Find the first non-array ref, and return its alias variable.  */
 209         tree p;
 210
 211         for (p = expr;
 212              TREE_CODE (p) == ARRAY_REF || TREE_CODE (p) == ARRAY_RANGE_REF;
 213              p = TREE_OPERAND (p, 0))
 214           ;
 215         return get_alias_var (p);
 216       }
 217       break;
 218     case COMPONENT_REF:
 219       {
 220 #if FIELD_BASED
 221         bool safe = true;
 222         tree p;
 223         for (p = expr;
 224              TREE_CODE (p) == COMPONENT_REF || TREE_CODE (p) == INDIRECT_REF;
 225              p = TREE_OPERAND (p, 0))
 226           {
 227             if (TREE_CODE (TREE_TYPE (p)) == UNION_TYPE
 228                 || TREE_CODE (TREE_TYPE (p)) == QUAL_UNION_TYPE)
 229               {
 230                 safe = false;
 231                 break;
 232               }
 233           }
 234         if (!safe)
 235           {
 236             for (p = expr; TREE_CODE (p) == COMPONENT_REF;
 237                  p = TREE_OPERAND (p, 0));
 238             return get_alias_var (p);
 239           }
 240         else
 241           {
 242             return get_alias_var (TREE_OPERAND (expr, 1));
 243           }
 244 #else
 245         /* Find the first non-component ref, and return its alias variable.  */
 246         tree p;
 247         for (p = expr; TREE_CODE (p) == COMPONENT_REF;
 248              p = TREE_OPERAND (p, 0));
 249         return get_alias_var (p);
 250 #endif
 251       }
 252       break;
 253     case REALPART_EXPR:
 254     case IMAGPART_EXPR:
 255     case NOP_EXPR:
 256     case CONVERT_EXPR:
 257     case FIX_TRUNC_EXPR:
 258     case FIX_CEIL_EXPR:
 259     case FIX_FLOOR_EXPR:
 260     case FIX_ROUND_EXPR:
 261     case ADDR_EXPR:
 262     case INDIRECT_REF:
 263     case BIT_FIELD_REF:
 264       /* If it's a ref or cast or conversion of something, get the
 265          alias var of the something.  */
 266       return get_alias_var (TREE_OPERAND (expr, 0));
 267       break;
 268
 269     default:
 270       return NULL;
 271     }
 272 }
 273
 274 /*  Perform conservative aliasing for an intraprocedural mode function
 275     call.  ARGS are the arguments that were passed to that function
 276     call.  */
 277
 278 static void
 279 intra_function_call (varray_type args)
 280 {
 281   size_t l = VARRAY_ACTIVE_SIZE (args);
 282   size_t i;
 283   alias_var av = get_alias_var (pta_global_var);
 284
 285   /* We assume assignments among the actual parameters.  */
 286   for (i = 0; i < l; i++)
 287     {
 288       alias_var argi = VARRAY_GENERIC_PTR (args, i);
 289       size_t j;
 290       for (j = 0; j < l; j++)
 291         {
 292           alias_var argj;
 293           if (i == j)
 294             continue;
 295           argj = VARRAY_GENERIC_PTR (args, j);
 296           /* Restricted pointers can't be aliased with other
 297              restricted pointers.  */
 298           if (!TYPE_RESTRICT (TREE_TYPE (ALIAS_VAR_DECL (argi)))
 299               || !TYPE_RESTRICT (TREE_TYPE (ALIAS_VAR_DECL (argj))))
 300             /* Do a bit of TBAA to avoid pointless assignments.  */
 301             if (alias_sets_conflict_p (get_alias_set (ALIAS_VAR_DECL (argi)),
 302                                        get_alias_set (ALIAS_VAR_DECL (argj))))
 303               current_alias_ops->simple_assign (current_alias_ops, argi, argj);
 304         }
 305     }
 306   /* We assume that an actual parameter can point to any global.  */
 307   for (i = 0; i < l; i++)
 308     {
 309       alias_var argav = VARRAY_GENERIC_PTR (args, i);
 310       /* Restricted pointers can't be aliased with other
 311          restricted pointers.  */
 312       if (!TYPE_RESTRICT (TREE_TYPE (ALIAS_VAR_DECL (argav)))
 313           || !TYPE_RESTRICT (TREE_TYPE (ALIAS_VAR_DECL (av))))
 314         {
 315           /* Arguments can alias globals, and whatever they point to
 316              can point to a global as well.  */
 317           current_alias_ops->simple_assign (current_alias_ops, argav, av);
 318         }
 319     }
 320 }
 321
 322 /* Put all pointers in a constructor in an array.  */
 323
 324 static void
 325 get_values_from_constructor (tree constructor, varray_type *vals,
 326                              bitmap addrargs, int *i)
 327 {
 328   tree elt_list;
 329   switch (TREE_CODE (constructor))
 330     {
 331     case CONSTRUCTOR:
 332       {
 333         for (elt_list = CONSTRUCTOR_ELTS (constructor);
 334              elt_list;
 335              elt_list = TREE_CHAIN (elt_list))
 336           {
 337             tree value = TREE_VALUE (elt_list);
 338             if (TREE_CODE (value) == TREE_LIST
 339                 || TREE_CODE (value) == CONSTRUCTOR)
 340               {
 341                 get_values_from_constructor (value, vals, addrargs, i);                       }
 342             else
 343               {
 344                 alias_var aav;
 345                 aav = get_alias_var (value);
 346                 if (aav)
 347                   VARRAY_PUSH_GENERIC_PTR (*vals, aav);
 348                 if (TREE_CODE (value) == ADDR_EXPR)
 349                   bitmap_set_bit (addrargs, *i);
 350                 *i = *i + 1;
 351               }
 352           }
 353       }
 354       break;
 355     case TREE_LIST:
 356       for (elt_list = constructor;
 357            elt_list;
 358            elt_list = TREE_CHAIN (elt_list))
 359         {
 360           get_values_from_constructor (TREE_VALUE (elt_list), vals, addrargs, i);
 361         }
 362       break;
 363     default:
 364       abort();
 365     }
 366 }
 367
 368 /* Deal with the possible return values of a call that we don't have
 369    actual PTA info about.  */
 370
 371 static void
 372 deal_with_call_aliasing (tree callargs, alias_var lhsAV)
 373 {
 374   tree arg, argp;
 375
 376   for (argp = callargs;
 377        argp;
 378        argp = TREE_CHAIN (argp))
 379     {
 380       arg = TREE_VALUE (argp);
 381       /* If we take the address of a variable directly in the
 382          argument, the return value could be the address of that
 383          variable.  */
 384       if (TREE_CODE (arg) == ADDR_EXPR)
 385         current_alias_ops->addr_assign (current_alias_ops, lhsAV,
 386                                         get_alias_var (arg));
 387       /* If we pass in a pointer, we could return that pointer.  */
 388       else if (POINTER_TYPE_P (TREE_TYPE (arg)))
 389         {
 390           alias_var argtv = get_alias_var (arg);
 391           if (argtv)
 392             current_alias_ops->simple_assign (current_alias_ops, lhsAV,
 393                                               argtv);
 394         }
 395     }
 396 }
 397
 398 /* Find the operand of the component ref that actually is doing
 399    something to the DECL  */
 400 static tree
 401 find_op_of_decl (tree cref)
 402 {
 403   while (!DECL_P (TREE_OPERAND (cref, 0)))
 404     {
 405       cref = TREE_OPERAND (cref, 0);
 406     }
 407   return cref;
 408 }
 409
 410
 411 /*  Tree walker that is the heart of the aliasing infrastructure.
 412     TP is a pointer to the current tree.
 413     WALK_SUBTREES specifies whether to continue traversing subtrees or
 414     not.
 415     Returns NULL_TREE when we should stop.
 416
 417     This function is the main part of the aliasing infrastructure. It
 418     walks the trees, calling the appropriate alias analyzer functions to process
 419     various statements.  */
 420
 421 static void
 422 find_func_aliases (tree stp)
 423 {
 424   if (TREE_CODE (stp) == RETURN_EXPR)
 425     {
 426       stp = TREE_OPERAND (stp, 0);
 427       if (!stp)
 428         return;
 429     }
 430
 431   if (TREE_CODE (stp) == MODIFY_EXPR
 432       || (DECL_P (stp) && DECL_INITIAL (stp) != NULL_TREE ))
 433     {
 434       tree op0, op1;
 435       alias_var lhsAV = NULL;
 436       alias_var rhsAV = NULL;
 437
 438       if (DECL_P (stp))
 439         {
 440           op0 = stp;
 441           op1 = DECL_INITIAL (stp);
 442         }
 443       else
 444         {
 445           op0 = TREE_OPERAND (stp, 0);
 446           op1 = TREE_OPERAND (stp, 1);
 447           if (TREE_CODE (op1) == WITH_SIZE_EXPR)
 448             op1 = TREE_OPERAND (op1, 0);
 449         }
 450
 451       /* lhsAV should always have an alias variable */
 452       lhsAV = get_alias_var (op0);
 453       if (!lhsAV)
 454         return;
 455       /* rhsAV might not have one, c.f. c = 5 */
 456       rhsAV = get_alias_var (op1);
 457 #if !FIELD_BASED
 458       while (TREE_CODE (op1) == COMPONENT_REF
 459              && TREE_CODE (TREE_OPERAND (op1, 0)) == COMPONENT_REF)
 460         {
 461           op1 = TREE_OPERAND (op1, 0);
 462         }
 463       while (TREE_CODE (op1) == BIT_FIELD_REF)
 464         {
 465           op1 = TREE_OPERAND (op1, 0);
 466         }
 467       /* Take care of fact that we may have multi-level component
 468          refs.  */
 469       if (TREE_CODE (op1) == COMPONENT_REF)
 470         op1 = find_op_of_decl (op1);
 471 #endif
 472
 473       /* You would think we could test rhsAV at the top, rather than
 474          50 separate times, but we can't, because it can be NULL for
 475          operator assignments, where we'd still collect the individual
 476          alias vars for the operator.  */
 477
 478       /* Note that structures are treated as a single alias
 479          variable, since we can disambiguate based on TBAA first,
 480          and fall back on points-to.  */
 481       /* x = <something> */
 482       if (is_gimple_variable (op0))
 483         {
 484           /* x = y */
 485           if (is_gimple_variable (op1))
 486             {
 487               if (rhsAV != NULL)
 488                 current_alias_ops->simple_assign (current_alias_ops, lhsAV,
 489                                                   rhsAV);
 490             }
 491           /* x = foo.y */
 492           else if (TREE_CODE (op1) == COMPONENT_REF
 493                    && DECL_P (TREE_OPERAND (op1, 0)))
 494             {
 495                  if (rhsAV != NULL)
 496                 current_alias_ops->simple_assign (current_alias_ops, lhsAV,
 497                                                   rhsAV);
 498             }
 499           /* x = (cast) [maybe-addr-expr] y */
 500           else if (is_gimple_cast (op1))
 501             {
 502               tree stripped_op1 = op1;
 503               STRIP_NOPS (stripped_op1);
 504               if (rhsAV != NULL)
 505                 {
 506                   if (TREE_CODE (stripped_op1) == ADDR_EXPR)
 507                     current_alias_ops->addr_assign (current_alias_ops, lhsAV,
 508                                                     rhsAV);
 509                   else
 510                     current_alias_ops->simple_assign (current_alias_ops, lhsAV,
 511                                                       rhsAV);
 512                 }
 513             }
 514           /* x = *y or x = foo->y */
 515           else if (TREE_CODE (op1) == INDIRECT_REF
 516                    || TREE_CODE (op1) == ARRAY_REF
 517                    || (TREE_CODE (op1) == COMPONENT_REF
 518                        && TREE_CODE (TREE_OPERAND (op1, 0)) == INDIRECT_REF))
 519             {
 520               if (rhsAV != NULL)
 521                 current_alias_ops->ptr_assign (current_alias_ops, lhsAV,
 522                                                rhsAV);
 523             }
 524           /* x = &y = x = &foo.y */
 525           else if (TREE_CODE (op1) == ADDR_EXPR)
 526             {
 527               if (rhsAV != NULL)
 528                 current_alias_ops->addr_assign (current_alias_ops, lhsAV,
 529                                                 rhsAV);
 530             }
 531           /* x = func(...) */
 532           else if (TREE_CODE (op1) == CALL_EXPR)
 533             {
 534               /* Heap assignment. These are __attribute__ malloc or
 535                  something, I'll deal with it later.  */
 536               if (0)
 537                 {}
 538               else
 539                 {
 540
 541                   /* NORETURN functions have no effect on aliasing.  */
 542                   if (call_may_return (op1))
 543                     {
 544                       varray_type args;
 545                       tree arg;
 546                       tree callop0, callop1;
 547                       int argnum;
 548
 549                       /* Collect the arguments */
 550                       VARRAY_GENERIC_PTR_INIT (args, 1, "Arguments");
 551                       bitmap_clear (addrargs);
 552                       callop1 = TREE_OPERAND (op1, 1);
 553                       callop0 = TREE_OPERAND (op1, 0);
 554                       for (arg = callop1, argnum = 0;
 555                            arg;
 556                            arg = TREE_CHAIN (arg), argnum++)
 557                         {
 558                           alias_var aav = get_alias_var (TREE_VALUE (arg));
 559                           if (aav)
 560                             {
 561                               VARRAY_PUSH_GENERIC_PTR (args, aav);
 562                               if (TREE_CODE (TREE_VALUE (arg)) == ADDR_EXPR)
 563                                 bitmap_set_bit (addrargs, argnum);
 564                             }
 565                         }
 566                       /* Simulate the call */
 567                       if (current_alias_ops->function_call (current_alias_ops, lhsAV,
 568                                                             get_alias_var (callop0),
 569                                                             args, addrargs))
 570                         {
 571                           if (call_may_clobber (op1)
 572                               && !current_alias_ops->ip
 573                               && flag_argument_noalias != 2)
 574                             {
 575                               intra_function_call (args);
 576                             }
 577                           if (POINTER_TYPE_P (TREE_TYPE (op0)))
 578                             deal_with_call_aliasing (callop1, lhsAV);
 579                         }
 580                     }
 581                 }
 582             }
 583           /* x = op (...) */
 584           else
 585             {
 586               bitmap_clear (addrargs);
 587               if (TREE_CODE (op1) == CONSTRUCTOR)
 588                 {
 589                   varray_type ops;
 590                   int i = 0;
 591                   VARRAY_GENERIC_PTR_INIT (ops, 1, "Operands");
 592                   get_values_from_constructor (op1, &ops, addrargs, &i);
 593                   current_alias_ops->op_assign (current_alias_ops, lhsAV,
 594                                                 ops, op1, addrargs);
 595                 }
 596               else
 597                 switch (TREE_CODE_CLASS (TREE_CODE (op1)))
 598                   {
 599                   case 'e':  /* an expression */
 600                   case 's':  /* an expression with side effects */
 601                   case '<':  /* a comparison expression */
 602                   case '1':  /* a unary arithmetic expression */
 603                   case 'r':  /* a reference */
 604                   case '2':  /* a binary arithmetic expression */
 605                     {
 606                       tree op;
 607                       varray_type ops;
 608                       int i;
 609                       VARRAY_GENERIC_PTR_INIT (ops, 1, "Operands");
 610                       for (i = 0; i < TREE_CODE_LENGTH (TREE_CODE (op1)); i++)
 611                         {
 612                           alias_var aav;
 613                           op = TREE_OPERAND (op1, i);
 614                           aav = get_alias_var (op);
 615                           if (aav)
 616                             VARRAY_PUSH_GENERIC_PTR (ops, aav);
 617                           if (TREE_CODE (op) == ADDR_EXPR)
 618                             bitmap_set_bit (addrargs, i);
 619                         }
 620                       current_alias_ops->op_assign (current_alias_ops, lhsAV,
 621                                                     ops, op1, addrargs);
 622                     }
 623                     break;
 624                   default:
 625                     break;
 626                   }
 627             }
 628         }
 629       /* *x = <something> */
 630       else
 631         {
 632           /* x.f = y  or x->f = y */
 633           if ((TREE_CODE (op0) == COMPONENT_REF
 634                || TREE_CODE (op0) == BIT_FIELD_REF)
 635               && is_gimple_variable (op1))
 636             {
 637               if (rhsAV != NULL)
 638                 current_alias_ops->simple_assign (current_alias_ops, lhsAV,
 639                                                   rhsAV);
 640             }
 641           /* x.f = &y or x->f = &y */
 642           else if (TREE_CODE (op0) == COMPONENT_REF
 643                    && TREE_CODE (op1) == ADDR_EXPR)
 644             {
 645               if (rhsAV != NULL)
 646                 current_alias_ops->addr_assign (current_alias_ops, lhsAV,
 647                                                 rhsAV);
 648             }
 649           /* *x.f = y or *x->f = y */
 650           else if ((TREE_CODE (op0) == INDIRECT_REF
 651                     || TREE_CODE (op0) == ARRAY_REF)
 652                    && TREE_CODE (TREE_OPERAND (op0, 0)) == COMPONENT_REF
 653                    && is_gimple_variable (op1))
 654             {
 655               if (rhsAV != NULL)
 656                 current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
 657                                                rhsAV);
 658             }
 659           /* *x = &y */
 660           else if ((TREE_CODE (op0) == INDIRECT_REF
 661                     || TREE_CODE (op0) == ARRAY_REF)
 662                    && TREE_CODE (op1) == ADDR_EXPR)
 663             {
 664               /* This becomes temp = &y and *x = temp .  */
 665               alias_var tempvar;
 666               tree temp = create_tmp_var_raw (void_type_node, "aliastmp");
 667               tempvar = current_alias_ops->add_var (current_alias_ops, temp);
 668               current_alias_ops->addr_assign (current_alias_ops, tempvar,
 669                                               rhsAV);
 670               current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
 671                                              tempvar);
 672             }
 673
 674           /* *x = *y */
 675           else if ((TREE_CODE (op0) == INDIRECT_REF
 676                     || TREE_CODE (op0) == ARRAY_REF)
 677                    && (TREE_CODE (op1) == INDIRECT_REF
 678                        || TREE_CODE (op1) == ARRAY_REF))
 679             {
 680               /* This becomes temp = *y and *x = temp .  */
 681               alias_var tempvar;
 682               tree temp;
 683               temp = create_tmp_var_raw (void_type_node, "aliastmp");
 684               tempvar = current_alias_ops->add_var (current_alias_ops, temp);
 685               current_alias_ops->ptr_assign (current_alias_ops, tempvar,
 686                                              rhsAV);
 687               current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
 688                                              tempvar);
 689             }
 690
 691           /* *x = (cast) y */
 692           else if ((TREE_CODE (op0) == INDIRECT_REF
 693                     || TREE_CODE (op0) == ARRAY_REF)
 694                    && is_gimple_cast (op1))
 695             {
 696               if (rhsAV != NULL)
 697                 {
 698                   /* This becomes temp = (cast) y and  *x = temp.  */
 699                   alias_var tempvar;
 700                   tree temp;
 701                   temp = create_tmp_var_raw (void_type_node, "aliastmp");
 702                   tempvar = current_alias_ops->add_var (current_alias_ops,
 703                                                         temp);
 704                   current_alias_ops->simple_assign (current_alias_ops,
 705                                                     tempvar, rhsAV);
 706                   current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
 707                                                  tempvar);
 708                 }
 709             }
 710           /* *x = <something else> */
 711           else
 712             {
 713               if (rhsAV != NULL)
 714                 current_alias_ops->assign_ptr (current_alias_ops, lhsAV,
 715                                                rhsAV);
 716             }
 717         }
 718     }
 719   /* Calls without return values.  */
 720   else if (TREE_CODE (stp) == CALL_EXPR)
 721     {
 722       alias_var callvar;
 723       varray_type args;
 724       tree arg;
 725       callvar = get_alias_var (TREE_OPERAND (stp, 0));
 726       if (callvar != NULL)
 727         {
 728
 729           /* NORETURN and CONST functions with no return value
 730              have no effect on aliasing (as may be seen above,
 731              const functions that return a value might have an
 732              effect on aliasing, since the return value can point
 733              to one of the arguments.  */
 734           if (call_may_clobber (stp))
 735             {
 736               int argnum;
 737               VARRAY_GENERIC_PTR_INIT (args, 1, "Arguments");
 738               bitmap_clear (addrargs);
 739               for (arg = TREE_OPERAND (stp, 1), argnum=0;
 740                    arg;
 741                    arg = TREE_CHAIN (arg), argnum++)
 742                 {
 743                   alias_var aav = get_alias_var (TREE_VALUE (arg));
 744                   if (aav)
 745                     {
 746                       VARRAY_PUSH_GENERIC_PTR (args, aav);
 747                       if (TREE_CODE (TREE_VALUE (arg)) == ADDR_EXPR)
 748                         bitmap_set_bit (addrargs, argnum);
 749                     }
 750
 751                 }
 752
 753               if (current_alias_ops->function_call (current_alias_ops, NULL,
 754                                                     callvar, args, addrargs))
 755                 if (!current_alias_ops->ip && flag_argument_noalias != 2)
 756                   intra_function_call (args);
 757             }
 758         }
 759   }
 760 }
 761
 762 /*  Create the alias_var for a function definition DECL, it's
 763     arguments, and it's return value. If FORCE is true, we force
 764     creation of the alias_var, regardless of whether one exists already.
 765
 766     This includes creation of alias_var's for
 767     - The function itself.
 768     - The arguments.
 769     - The return value.  */
 770
 771 static alias_var
 772 create_fun_alias_var (tree decl, int force)
 773 {
 774   alias_var avar, retvar;
 775   tree rdecl;
 776   varray_type params = NULL;
 777
 778   if (!force)
 779     {
 780       if (DECL_PTA_ALIASVAR (decl))
 781         return DECL_PTA_ALIASVAR (decl);
 782     }
 783
 784   VARRAY_GENERIC_PTR_INIT (params, 1, "Arguments");
 785   if (DECL_ARGUMENTS (decl) != NULL)
 786     {
 787       tree arg;
 788       for (arg = DECL_ARGUMENTS (decl); arg; arg = TREE_CHAIN (arg))
 789         {
 790           alias_var var = get_alias_var (arg);
 791           VARRAY_PUSH_GENERIC_PTR (params, var);
 792           /* Incoming pointers can point to pta_global_var, unless
 793              either we are interprocedural, or we can do ip on all
 794              statics + this function has been defined + it's not an
 795              external function.  */
 796           if (POINTER_TYPE_P (TREE_TYPE (arg))
 797               && !current_alias_ops->ip
 798               /* FIXME: Need to let analyzer decide in partial case.  */
 799               && (!current_alias_ops->ip_partial
 800                   || !cgraph_local_info (decl)->local))
 801             current_alias_ops->simple_assign (current_alias_ops, var,
 802                                               get_alias_var (pta_global_var));
 803         }
 804     }
 805   else if (TYPE_ARG_TYPES (TREE_TYPE (decl)) != NULL)
 806     {
 807       tree arg;
 808       /* FIXME: Handle varargs */
 809       for (arg = TYPE_ARG_TYPES (TREE_TYPE (decl));
 810            arg && TREE_VALUE (arg) != void_type_node;
 811            arg = TREE_CHAIN (arg))
 812         {
 813           tree fakedecl = create_tmp_var_raw (TREE_VALUE (arg), "normarg");
 814           alias_var var;
 815           DECL_CONTEXT (fakedecl) = current_function_decl;
 816           var = get_alias_var (fakedecl);
 817           VARRAY_PUSH_GENERIC_PTR (params, var);
 818
 819           /* Incoming pointers can point to pta_global_var, unless
 820              either we are interprocedural, or we can do ip on all
 821              statics + this function has been defined + it's not an
 822              external function.  */
 823           if (POINTER_TYPE_P (TREE_TYPE (fakedecl))
 824               && !current_alias_ops->ip
 825               /* FIXME: need to let analyzer decide in partial case.  */
 826               && (!current_alias_ops->ip_partial
 827                   || !TREE_STATIC (decl)
 828                   || TREE_PUBLIC (decl)))
 829             current_alias_ops->simple_assign (current_alias_ops, var,
 830                                               get_alias_var (pta_global_var));
 831         }
 832     }
 833   /* Functions declared like void f() are *not* equivalent to void
 834      f(void). You can pass an argument to them. Thus, we need to
 835      create some fake argument that would alias any actuals that get
 836      passed to our function.  */
 837   else
 838     {
 839       tree fakedecl = create_tmp_var_raw (void_type_node, "fakearg");
 840       alias_var fakevar;
 841       DECL_CONTEXT (fakedecl) = current_function_decl;
 842       fakevar = get_alias_var (fakedecl);
 843       VARRAY_PUSH_GENERIC_PTR (params, fakevar);
 844     }
 845
 846   if (!DECL_RESULT (decl))
 847     {
 848       rdecl = create_tmp_var_raw (TREE_TYPE (TREE_TYPE (decl)), "_rv_");
 849       retvar = current_alias_ops->add_var (current_alias_ops, rdecl);
 850       DECL_PTA_ALIASVAR (rdecl) = retvar;
 851     }
 852   else
 853     {
 854       retvar = current_alias_ops->add_var (current_alias_ops,
 855                                            DECL_RESULT (decl));
 856       DECL_PTA_ALIASVAR (DECL_RESULT (decl)) = retvar;
 857     }
 858   VARRAY_PUSH_GENERIC_PTR (alias_vars, retvar);
 859   ALIAS_VAR_VARNUM (retvar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;
 860   avar = current_alias_ops->add_var (current_alias_ops, decl);
 861   VARRAY_PUSH_GENERIC_PTR (alias_vars, avar);
 862   ALIAS_VAR_VARNUM (avar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;
 863
 864   current_alias_ops->function_def (current_alias_ops, avar, params, retvar);
 865   DECL_PTA_ALIASVAR (decl) = avar;
 866
 867   /* FIXME: Also, if this is a defining declaration then add the annotation
 868      to all extern definitions of the function.  */
 869   return avar;
 870 }
 871
 872 /*  Create an alias variable for a pointer-to-member function DECL of
 873     type TYPE, it's arguments, and it's return value.
 874     Returns the alias_var for the PTF.
 875
 876     This includes creating alias_var's for
 877     - The function itself.
 878     - The arguments.
 879     - The return value.  */
 880
 881 static alias_var
 882 create_fun_alias_var_ptf (tree decl, tree type)
 883 {
 884   alias_var avar, retvar;
 885   tree rdecl;
 886   varray_type params = NULL;
 887
 888   if (DECL_PTA_ALIASVAR (decl))
 889     return DECL_PTA_ALIASVAR (decl);
 890
 891   VARRAY_GENERIC_PTR_INIT (params, 1, "Arguments");
 892
 893   if (TYPE_ARG_TYPES  (type) != NULL)
 894     {
 895       tree arg;
 896       /* FIXME: Handle varargs */
 897       for (arg = TYPE_ARG_TYPES (type);
 898            arg && TREE_VALUE (arg) != void_type_node;
 899            arg = TREE_CHAIN (arg))
 900         {
 901           tree fakedecl = create_tmp_var_raw (TREE_VALUE (arg), "ptfarg");
 902           alias_var var;
 903           DECL_CONTEXT (fakedecl) = DECL_CONTEXT (decl);
 904           var = get_alias_var (fakedecl);
 905           VARRAY_PUSH_GENERIC_PTR (params, var);
 906         }
 907     }
 908   /* Functions declared like void f() are *not* equivalent to void
 909      f(void). You can pass an argument to them. Thus, we need to
 910      create some fake argument that would alias any actuals that get
 911      passed to our function.  */
 912   else
 913     {
 914       tree fakedecl = create_tmp_var_raw (void_type_node, "fakearg");
 915       alias_var fakevar;
 916       DECL_CONTEXT (fakedecl) = DECL_CONTEXT (decl);
 917       fakevar = get_alias_var (fakedecl);
 918       VARRAY_PUSH_GENERIC_PTR (params, fakevar);
 919     }
 920
 921   rdecl = create_tmp_var_raw (TREE_TYPE (type), "_rv_");
 922   retvar = current_alias_ops->add_var (current_alias_ops, rdecl);
 923   VARRAY_PUSH_GENERIC_PTR (alias_vars, retvar);
 924   ALIAS_VAR_VARNUM (retvar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;
 925
 926   avar = current_alias_ops->add_var (current_alias_ops, decl);
 927   VARRAY_PUSH_GENERIC_PTR (alias_vars, avar);
 928   ALIAS_VAR_VARNUM (avar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;
 929
 930   current_alias_ops->function_def (current_alias_ops, avar, params, retvar);
 931   DECL_PTA_ALIASVAR (decl) = avar;
 932
 933   return avar;
 934 }
 935
 936 /*  Create the alias_var for a *_DECL node DECL.
 937     Returns the alias_var for DECL.
 938
 939     This function also handles creation of alias_var's for PTF
 940     variables.  */
 941
 942 static alias_var
 943 create_alias_var (tree decl)
 944 {
 945   alias_var avar;
 946
 947   if (!DECL_P (decl))
 948     abort ();
 949
 950   if (DECL_P (decl))
 951     {
 952       if (DECL_PTA_ALIASVAR (decl))
 953         return DECL_PTA_ALIASVAR (decl);
 954     }
 955
 956   if (POINTER_TYPE_P (TREE_TYPE (decl))
 957       && TREE_CODE (TREE_TYPE (TREE_TYPE (decl))) == FUNCTION_TYPE)
 958     {
 959       avar = create_fun_alias_var_ptf (decl, TREE_TYPE (TREE_TYPE (decl)));
 960     }
 961   else
 962     avar = current_alias_ops->add_var (current_alias_ops, decl);
 963
 964   if (DECL_P (decl))
 965     {
 966       DECL_PTA_ALIASVAR (decl) = avar;
 967     }
 968
 969   VARRAY_PUSH_GENERIC_PTR (alias_vars, avar);
 970   ALIAS_VAR_VARNUM (avar) = VARRAY_ACTIVE_SIZE (alias_vars) - 1;
 971   return avar;
 972 }
 973
 974 /* Create points-to sets for the current function.  */
 975
 976 static void
 977 create_alias_vars (void)
 978 {
 979   basic_block bb;
 980 #if HAVE_BANSHEE
 981   if (flag_tree_points_to == PTA_ANDERSEN)
 982     current_alias_ops = andersen_alias_ops;
 983   else
 984 #endif
 985    {
 986      current_alias_ops = NULL;
 987      flag_tree_points_to = PTA_NONE;
 988      return;
 989    }
 990
 991   pta_global_var = build_decl (VAR_DECL, get_identifier (".pta_global_var"),
 992                                size_type_node);
 993   DECL_ARTIFICIAL (pta_global_var) = 1;
 994   TREE_READONLY (pta_global_var) = 1;
 995   DECL_EXTERNAL (pta_global_var) = 0;
 996   TREE_STATIC (pta_global_var) = 1;
 997   TREE_USED (pta_global_var) = 1;
 998   DECL_CONTEXT (pta_global_var) = current_function_decl;
 999   TREE_THIS_VOLATILE (pta_global_var) = 1;
1000   TREE_ADDRESSABLE (pta_global_var) = 0;
1001
1002   init_alias_vars ();
1003
1004   DECL_PTA_ALIASVAR (current_function_decl) = NULL;
1005   get_alias_var (current_function_decl);
1006
1007   /* First, walk the variables and their DECL_INITIAL's */
1008   if (cfun->unexpanded_var_list)
1009     {
1010       tree vars, var;
1011       for (vars = cfun->unexpanded_var_list; vars; vars = TREE_CHAIN (vars))
1012         {
1013           var = TREE_VALUE (vars);
1014           if (TREE_CODE (var) != LABEL_DECL
1015               && TREE_STATIC (var)
1016               && DECL_INITIAL (var))
1017             find_func_aliases (var);
1018         }
1019     }
1020
1021   /* Now walk all statements and derive aliases.  */
1022   FOR_EACH_BB (bb)
1023     {
1024       block_stmt_iterator bsi;
1025       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1026         find_func_aliases (bsi_stmt (bsi));
1027     }
1028
1029   pta_global_var = NULL_TREE;
1030 }
1031
1032 struct tree_opt_pass pass_build_pta =
1033 {
1034   "pta",                                /* name */
1035   NULL,                                 /* gate */
1036   create_alias_vars,                    /* execute */
1037   NULL,                                 /* sub */
1038   NULL,                                 /* next */
1039   0,                                    /* static_pass_number */
1040   TV_TREE_PTA,                          /* tv_id */
1041   PROP_cfg,                             /* properties_required */
1042   PROP_pta,                             /* properties_provided */
1043   0,                                    /* properties_destroyed */
1044   0,                                    /* todo_flags_start */
1045   0                                     /* todo_flags_finish */
1046 };
1047
1048
1049 /* Delete created points-to sets.  */
1050
1051 static void
1052 delete_alias_vars (void)
1053 {
1054   size_t i;
1055
1056   if (flag_tree_points_to != PTA_ANDERSEN)
1057     return;
1058
1059   for (i = 0; i < VARRAY_ACTIVE_SIZE (local_alias_vars); i++)
1060     {
1061       tree key = VARRAY_TREE (local_alias_vars, i);
1062       if (DECL_P (key))
1063         DECL_PTA_ALIASVAR (key) = NULL;
1064       else
1065         abort ();
1066     }
1067
1068   for (i = 0; i < VARRAY_ACTIVE_SIZE (local_alias_varnums); i ++)
1069     VARRAY_GENERIC_PTR (alias_vars, VARRAY_INT (local_alias_varnums, i)) = NULL;
1070   if (!current_alias_ops->ip && !current_alias_ops->ip_partial)
1071     {
1072       /*      VARRAY_CLEAR (alias_vars); */
1073       VARRAY_CLEAR (local_alias_vars);
1074       VARRAY_CLEAR (local_alias_varnums);
1075     }
1076   BITMAP_XFREE (addrargs);
1077   current_alias_ops->cleanup (current_alias_ops);
1078 }
1079
1080 struct tree_opt_pass pass_del_pta =
1081 {
1082   "pta",                                /* name */
1083   NULL,                                 /* gate */
1084   delete_alias_vars,                    /* execute */
1085   NULL,                                 /* sub */
1086   NULL,                                 /* next */
1087   0,                                    /* static_pass_number */
1088   TV_TREE_PTA,                          /* tv_id */
1089   PROP_pta,                             /* properties_required */
1090   0,                                    /* properties_provided */
1091   PROP_pta,                             /* properties_destroyed */
1092   0,                                    /* todo_flags_start */
1093   0                                     /* todo_flags_finish */
1094 };
1095
1096
1097 /*  Initialize points-to analysis machinery.  */
1098
1099 void
1100 init_alias_vars (void)
1101 {
1102   current_alias_ops->init (current_alias_ops);
1103   addrargs = BITMAP_XMALLOC ();
1104   VARRAY_TREE_INIT (local_alias_vars, 10, "Local alias vars");
1105   VARRAY_INT_INIT (local_alias_varnums, 10, "Local alias varnums");
1106   if ((!current_alias_ops->ip && !current_alias_ops->ip_partial)
1107       || alias_vars == NULL)
1108     VARRAY_GENERIC_PTR_INIT (alias_vars, 10, "Alias vars");
1109 }
1110
1111 /* Return true if PTR can't point to anything (i.e. it has an empty
1112    points-to set.  */
1113 bool
1114 empty_points_to_set (tree ptr)
1115 {
1116  alias_var ptrtv;
1117
1118 #if !FIELD_BASED
1119 #else
1120   if (TREE_CODE (ptr) == COMPONENT_REF)
1121     ptr = TREE_OPERAND (ptr, 1);
1122 #endif
1123
1124   if (DECL_P (ptr))
1125     {
1126       ptrtv = DECL_PTA_ALIASVAR (ptr);
1127       if (!ptrtv)
1128         return true;
1129     }
1130   else
1131     abort ();
1132
1133   return current_alias_ops->empty_points_to_set (current_alias_ops, ptrtv);
1134 }
1135
1136 /* Return true if PTR and VAR have the same points-to set.  */
1137
1138 bool
1139 same_points_to_set (tree ptr, tree var)
1140 {
1141   alias_var ptrtv, vartv;
1142
1143 #if !FIELD_BASED
1144 #else
1145   if (TREE_CODE (ptr) == COMPONENT_REF)
1146     ptr = TREE_OPERAND (ptr, 1);
1147   if (TREE_CODE (var) == COMPONENT_REF)
1148     var = TREE_OPERAND (var, 1);
1149 #endif
1150
1151   if (ptr == var)
1152     return true;
1153
1154   if (DECL_P (ptr))
1155     {
1156       ptrtv = DECL_PTA_ALIASVAR (ptr);
1157       if (!ptrtv)
1158         return false;
1159     }
1160   else
1161     abort ();
1162
1163   if (DECL_P (var))
1164     {
1165       vartv = DECL_PTA_ALIASVAR (var);
1166       if (!vartv)
1167         return false;
1168     }
1169   else
1170     abort ();
1171
1172   return current_alias_ops->same_points_to_set (current_alias_ops, vartv, ptrtv);
1173 }
1174
1175 /*  Determine whether two variables (PTR and VAR) may-alias.
1176     Returns TRUE if PTR may-alias VAR.  */
1177
1178 bool
1179 ptr_may_alias_var (tree ptr, tree var)
1180 {
1181   alias_var ptrtv, vartv;
1182
1183 #if !FIELD_BASED
1184 #else
1185   if (TREE_CODE (ptr) == COMPONENT_REF)
1186     ptr = TREE_OPERAND (ptr, 1);
1187   if (TREE_CODE (var) == COMPONENT_REF)
1188     var = TREE_OPERAND (var, 1);
1189 #endif
1190
1191   if (ptr == var)
1192     return true;
1193
1194   if (DECL_P (ptr))
1195     {
1196       ptrtv = DECL_PTA_ALIASVAR (ptr);
1197       if (!ptrtv)
1198         return false;
1199     }
1200   else
1201     abort ();
1202
1203   if (DECL_P (var))
1204     {
1205       vartv = DECL_PTA_ALIASVAR (var);
1206       if (!vartv)
1207         return false;
1208     }
1209   else
1210     abort ();
1211
1212   return current_alias_ops->may_alias (current_alias_ops, ptrtv, vartv);
1213 }
1214
1215 #define MASK_POINTER(P) ((unsigned)((unsigned long)(P) & 0xffff))
1216
1217 const char *
1218 alias_get_name (tree t)
1219 {
1220   const char *name;
1221
1222 #if FIELD_BASED
1223   if (TREE_CODE (t) == FIELD_DECL)
1224     {
1225       /* First get the name of the field, then the prefix, then smash them
1226          together.  */
1227       const char *fieldname = IDENTIFIER_POINTER (DECL_NAME (t));
1228       const char *prefix = alias_get_name (DECL_CONTEXT (t));
1229       char *smashed;
1230       size_t neededlen = strlen (fieldname) + strlen (prefix) + 2;
1231       smashed = ggc_alloc (neededlen);
1232       sprintf (smashed, "%s.%s", prefix, fieldname);
1233       name = smashed;
1234
1235     }
1236   else if (TYPE_P (t))
1237     {
1238       if (TYPE_NAME (t) && IDENTIFIER_POINTER (TYPE_NAME (t)))
1239         name = IDENTIFIER_POINTER (TYPE_NAME (t));
1240       else
1241         name = "<unnamed type>";
1242     }
1243   else
1244 #endif
1245     {
1246       if (TREE_CODE (t) == FUNCTION_DECL)
1247         name = IDENTIFIER_POINTER (DECL_NAME (t));
1248       else if (TREE_CODE (t) == RESULT_DECL)
1249         name = "<return value>";
1250       else
1251         name = get_name (t);
1252     }
1253
1254   if (!name)
1255     {
1256       char *namep;
1257       /* 2 = UF
1258          4 = the masked pointer
1259          2 = the <> around it
1260          1 = the terminator.  */
1261       namep = ggc_alloc (2 + 4 + 2 + 1);
1262       sprintf (namep, "<UV%x>", MASK_POINTER (t));
1263       return namep;
1264     }
1265
1266   return name;
1267 }
1268
1269 #include "gt-tree-alias-common.h"