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