gcc/tree-ssa-ccp.c

   1 /* Conditional constant propagation pass for the GNU compiler.
   2    Copyright (C) 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
   3    Adapted from original RTL SSA-CCP by Daniel Berlin <dberlin@dberlin.org>
   4    Adapted to GIMPLE trees by Diego Novillo <dnovillo@redhat.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it
   9 under the terms of the GNU General Public License as published by the
  10 Free Software Foundation; either version 2, or (at your option) any
  11 later version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT
  14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to the Free
  20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  21 02111-1307, USA.  */
  22
  23 /* Conditional constant propagation.
  24
  25    References:
  26
  27      Constant propagation with conditional branches,
  28      Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
  29
  30      Building an Optimizing Compiler,
  31      Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
  32
  33      Advanced Compiler Design and Implementation,
  34      Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6  */
  35
  36 #include "config.h"
  37 #include "system.h"
  38 #include "coretypes.h"
  39 #include "tm.h"
  40 #include "errors.h"
  41 #include "ggc.h"
  42 #include "tree.h"
  43 #include "langhooks.h"
  44
  45 /* These RTL headers are needed for basic-block.h.  */
  46 #include "rtl.h"
  47 #include "tm_p.h"
  48 #include "hard-reg-set.h"
  49 #include "basic-block.h"
  50
  51 #include "diagnostic.h"
  52 #include "tree-inline.h"
  53 #include "tree-flow.h"
  54 #include "tree-gimple.h"
  55 #include "tree-dump.h"
  56 #include "tree-pass.h"
  57 #include "timevar.h"
  58 #include "expr.h"
  59 #include "flags.h"
  60
  61
  62 /* Possible lattice values.  */
  63 typedef enum
  64 {
  65   UNINITIALIZED = 0,
  66   UNDEFINED,
  67   CONSTANT,
  68   VARYING
  69 } latticevalue;
  70
  71 /* Use the TREE_VISITED bitflag to mark statements and PHI nodes that have
  72    been deemed VARYING and shouldn't be simulated again.  */
  73 #define DONT_SIMULATE_AGAIN(T)  TREE_VISITED (T)
  74
  75 /* Main structure for CCP.  Contains the lattice value and, if it's a
  76     constant, the constant value.  */
  77 typedef struct
  78 {
  79   latticevalue lattice_val;
  80   tree const_val;
  81 } value;
  82
  83 /* A bitmap to keep track of executable blocks in the CFG.  */
  84 static sbitmap executable_blocks;
  85
  86 /* Array of control flow edges on the worklist.  */
  87 static GTY(()) varray_type cfg_blocks = NULL;
  88
  89 static unsigned int cfg_blocks_num = 0;
  90 static int cfg_blocks_tail;
  91 static int cfg_blocks_head;
  92
  93 static sbitmap bb_in_list;
  94
  95 /* This is used to track the current value of each variable.  */
  96 static value *value_vector;
  97
  98 /* Worklist of SSA edges which will need reexamination as their definition
  99    has changed.  SSA edges are def-use edges in the SSA web.  For each
 100    edge, we store the definition statement or PHI node D.  The destination
 101    nodes that need to be visited are accessed using immediate_uses
 102    (D).  */
 103 static GTY(()) varray_type ssa_edges;
 104
 105 /* Identical to SSA_EDGES.  For performance reasons, the list of SSA
 106    edges is split into two.  One contains all SSA edges who need to be
 107    reexamined because their lattice value changed to varying (this
 108    worklist), and the other contains all other SSA edges to be
 109    reexamined (ssa_edges).
 110
 111    Since most values in the program are varying, the ideal situation
 112    is to move them to that lattice value as quickly as possible.
 113    Thus, it doesn't make sense to process any other type of lattice
 114    value until all varying values are propagated fully, which is one
 115    thing using the varying worklist achieves.  In addition, if you
 116    don't use a separate worklist for varying edges, you end up with
 117    situations where lattice values move from
 118    undefined->constant->varying instead of undefined->varying.
 119 */
 120 static GTY(()) varray_type varying_ssa_edges;
 121
 122
 123 static void initialize (void);
 124 static void finalize (void);
 125 static void visit_phi_node (tree);
 126 static tree ccp_fold (tree);
 127 static value cp_lattice_meet (value, value);
 128 static void visit_stmt (tree);
 129 static void visit_cond_stmt (tree);
 130 static void visit_assignment (tree);
 131 static void add_var_to_ssa_edges_worklist (tree, value);
 132 static void add_outgoing_control_edges (basic_block);
 133 static void add_control_edge (edge);
 134 static void def_to_varying (tree);
 135 static void set_lattice_value (tree, value);
 136 static void simulate_block (basic_block);
 137 static void simulate_stmt (tree);
 138 static void substitute_and_fold (void);
 139 static value evaluate_stmt (tree);
 140 static void dump_lattice_value (FILE *, const char *, value);
 141 static bool replace_uses_in (tree, bool *);
 142 static latticevalue likely_value (tree);
 143 static tree get_rhs (tree);
 144 static void set_rhs (tree *, tree);
 145 static value *get_value (tree);
 146 static value get_default_value (tree);
 147 static tree ccp_fold_builtin (tree, tree);
 148 static bool get_strlen (tree, tree *, bitmap);
 149 static inline bool cfg_blocks_empty_p (void);
 150 static void cfg_blocks_add (basic_block);
 151 static basic_block cfg_blocks_get (void);
 152 static bool need_imm_uses_for (tree var);
 153
 154 /* Process an SSA edge worklist.  WORKLIST is the SSA edge worklist to
 155    drain. This pops statements off the given WORKLIST and processes
 156    them until there are no more statements on WORKLIST.  */
 157
 158 static void
 159 process_ssa_edge_worklist (varray_type *worklist)
 160 {
 161   /* Drain the entire worklist.  */
 162   while (VARRAY_ACTIVE_SIZE (*worklist) > 0)
 163     {
 164       /* Pull the statement to simulate off the worklist.  */
 165       tree stmt = VARRAY_TOP_TREE (*worklist);
 166       stmt_ann_t ann = stmt_ann (stmt);
 167       VARRAY_POP (*worklist);
 168
 169       /* visit_stmt can "cancel" reevaluation of some statements.
 170          If it does, then in_ccp_worklist will be zero.  */
 171       if (ann->in_ccp_worklist)
 172         {
 173           ann->in_ccp_worklist = 0;
 174           simulate_stmt (stmt);
 175         }
 176     }
 177 }
 178
 179 /* Main entry point for SSA Conditional Constant Propagation.  FNDECL is
 180    the declaration for the function to optimize.
 181
 182    On exit, VARS_TO_RENAME will contain the symbols that have been exposed by
 183    the propagation of ADDR_EXPR expressions into pointer dereferences and need
 184    to be renamed into SSA.
 185
 186    PHASE indicates which dump file from the DUMP_FILES array to use when
 187    dumping debugging information.  */
 188
 189 static void
 190 tree_ssa_ccp (void)
 191 {
 192   initialize ();
 193
 194   /* Iterate until the worklists are empty.  */
 195   while (!cfg_blocks_empty_p ()
 196          || VARRAY_ACTIVE_SIZE (ssa_edges) > 0
 197          || VARRAY_ACTIVE_SIZE (varying_ssa_edges) > 0)
 198     {
 199       if (!cfg_blocks_empty_p ())
 200         {
 201           /* Pull the next block to simulate off the worklist.  */
 202           basic_block dest_block = cfg_blocks_get ();
 203           simulate_block (dest_block);
 204         }
 205
 206       /* In order to move things to varying as quickly as
 207          possible,process the VARYING_SSA_EDGES worklist first.  */
 208       process_ssa_edge_worklist (&varying_ssa_edges);
 209
 210       /* Now process the SSA_EDGES worklist.  */
 211       process_ssa_edge_worklist (&ssa_edges);
 212     }
 213
 214   /* Now perform substitutions based on the known constant values.  */
 215   substitute_and_fold ();
 216
 217   /* Now cleanup any unreachable code.  */
 218   cleanup_tree_cfg ();
 219
 220   /* Free allocated memory.  */
 221   finalize ();
 222
 223   /* Debugging dumps.  */
 224   if (dump_file && (dump_flags & TDF_DETAILS))
 225     {
 226       dump_referenced_vars (dump_file);
 227       fprintf (dump_file, "\n\n");
 228     }
 229 }
 230
 231 static bool
 232 gate_ccp (void)
 233 {
 234   return flag_tree_ccp != 0;
 235 }
 236
 237 struct tree_opt_pass pass_ccp =
 238 {
 239   "ccp",                                /* name */
 240   gate_ccp,                             /* gate */
 241   tree_ssa_ccp,                         /* execute */
 242   NULL,                                 /* sub */
 243   NULL,                                 /* next */
 244   0,                                    /* static_pass_number */
 245   TV_TREE_CCP,                          /* tv_id */
 246   PROP_cfg | PROP_ssa,                  /* properties_required */
 247   0,                                    /* properties_provided */
 248   0,                                    /* properties_destroyed */
 249   0,                                    /* todo_flags_start */
 250   TODO_dump_func | TODO_rename_vars
 251     | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
 252 };
 253
 254
 255 /* Get the constant value associated with variable VAR.  */
 256
 257 static value *
 258 get_value (tree var)
 259 {
 260   value *val;
 261
 262 #if defined ENABLE_CHECKING
 263   if (TREE_CODE (var) != SSA_NAME)
 264     abort ();
 265 #endif
 266
 267   val = &value_vector[SSA_NAME_VERSION (var)];
 268   if (val->lattice_val == UNINITIALIZED)
 269     *val = get_default_value (var);
 270
 271   return val;
 272 }
 273
 274
 275 /* Simulate the execution of BLOCK.  Evaluate the statement associated
 276    with each variable reference inside the block.  */
 277
 278 static void
 279 simulate_block (basic_block block)
 280 {
 281   tree phi;
 282
 283   /* There is nothing to do for the exit block.  */
 284   if (block == EXIT_BLOCK_PTR)
 285     return;
 286
 287   if (dump_file && (dump_flags & TDF_DETAILS))
 288     fprintf (dump_file, "\nSimulating block %d\n", block->index);
 289
 290   /* Always simulate PHI nodes, even if we have simulated this block
 291      before.  */
 292   for (phi = phi_nodes (block); phi; phi = PHI_CHAIN (phi))
 293     visit_phi_node (phi);
 294
 295   /* If this is the first time we've simulated this block, then we
 296      must simulate each of its statements.  */
 297   if (!TEST_BIT (executable_blocks, block->index))
 298     {
 299       block_stmt_iterator j;
 300       unsigned int normal_edge_count;
 301       edge e, normal_edge;
 302
 303       /* Note that we have simulated this block.  */
 304       SET_BIT (executable_blocks, block->index);
 305
 306       for (j = bsi_start (block); !bsi_end_p (j); bsi_next (&j))
 307         visit_stmt (bsi_stmt (j));
 308
 309       /* We can not predict when abnormal edges will be executed, so
 310          once a block is considered executable, we consider any
 311          outgoing abnormal edges as executable.
 312
 313          At the same time, if this block has only one successor that is
 314          reached by non-abnormal edges, then add that successor to the
 315          worklist.  */
 316       normal_edge_count = 0;
 317       normal_edge = NULL;
 318       for (e = block->succ; e; e = e->succ_next)
 319         {
 320           if (e->flags & EDGE_ABNORMAL)
 321             {
 322               add_control_edge (e);
 323             }
 324           else
 325             {
 326               normal_edge_count++;
 327               normal_edge = e;
 328             }
 329         }
 330
 331         if (normal_edge_count == 1)
 332           add_control_edge (normal_edge);
 333     }
 334 }
 335
 336
 337 /* Follow the def-use edges for statement DEF_STMT and simulate all the
 338    statements reached by it.  */
 339
 340 static void
 341 simulate_stmt (tree use_stmt)
 342 {
 343   basic_block use_bb = bb_for_stmt (use_stmt);
 344
 345   if (dump_file && (dump_flags & TDF_DETAILS))
 346     {
 347       fprintf (dump_file, "\nSimulating statement (from ssa_edges): ");
 348       print_generic_stmt (dump_file, use_stmt, dump_flags);
 349     }
 350
 351   if (TREE_CODE (use_stmt) == PHI_NODE)
 352     {
 353       /* PHI nodes are always visited, regardless of whether or not the
 354          destination block is executable.  */
 355       visit_phi_node (use_stmt);
 356     }
 357   else if (TEST_BIT (executable_blocks, use_bb->index))
 358     {
 359       /* Otherwise, visit the statement containing the use reached by
 360          DEF, only if the destination block is marked executable.  */
 361       visit_stmt (use_stmt);
 362     }
 363 }
 364
 365
 366 /* Perform final substitution and folding.  After this pass the program
 367    should still be in SSA form.  */
 368
 369 static void
 370 substitute_and_fold (void)
 371 {
 372   basic_block bb;
 373
 374   if (dump_file && (dump_flags & TDF_DETAILS))
 375     fprintf (dump_file,
 376              "\nSubstituing constants and folding statements\n\n");
 377
 378   /* Substitute constants in every statement of every basic block.  */
 379   FOR_EACH_BB (bb)
 380     {
 381       block_stmt_iterator i;
 382       tree phi;
 383
 384       /* Propagate our known constants into PHI nodes.  */
 385       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 386         {
 387           int i;
 388
 389           for (i = 0; i < PHI_NUM_ARGS (phi); i++)
 390             {
 391               value *new_val;
 392               tree *orig_p = &PHI_ARG_DEF (phi, i);
 393
 394               if (! SSA_VAR_P (*orig_p))
 395                 break;
 396
 397               new_val = get_value (*orig_p);
 398               if (new_val->lattice_val == CONSTANT
 399                   && may_propagate_copy (*orig_p, new_val->const_val))
 400                 *orig_p = new_val->const_val;
 401             }
 402         }
 403
 404       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
 405         {
 406           bool replaced_address;
 407           tree stmt = bsi_stmt (i);
 408
 409           /* Skip statements that have been folded already.  */
 410           if (stmt_modified_p (stmt) || !is_exec_stmt (stmt))
 411             continue;
 412
 413           /* Replace the statement with its folded version and mark it
 414              folded.  */
 415           if (dump_file && (dump_flags & TDF_DETAILS))
 416             {
 417               fprintf (dump_file, "Line %d: replaced ", get_lineno (stmt));
 418               print_generic_stmt (dump_file, stmt, TDF_SLIM);
 419             }
 420
 421           if (replace_uses_in (stmt, &replaced_address))
 422             {
 423               bool changed = fold_stmt (bsi_stmt_ptr (i));
 424               stmt = bsi_stmt(i);
 425               modify_stmt (stmt);
 426               /* If we folded a builtin function, we'll likely
 427                  need to rename VDEFs.  */
 428               if (replaced_address || changed)
 429                 mark_new_vars_to_rename (stmt, vars_to_rename);
 430             }
 431
 432           if (dump_file && (dump_flags & TDF_DETAILS))
 433             {
 434               fprintf (dump_file, " with ");
 435               print_generic_stmt (dump_file, stmt, TDF_SLIM);
 436               fprintf (dump_file, "\n");
 437             }
 438         }
 439     }
 440 }
 441
 442
 443 /* Loop through the PHI_NODE's parameters for BLOCK and compare their
 444    lattice values to determine PHI_NODE's lattice value.  The value of a
 445    PHI node is determined calling cp_lattice_meet() with all the arguments
 446    of the PHI node that are incoming via executable edges.  */
 447
 448 static void
 449 visit_phi_node (tree phi)
 450 {
 451   bool short_circuit = 0;
 452   value phi_val, *curr_val;
 453   int i;
 454
 455   /* If the PHI node has already been deemed to be VARYING, don't simulate
 456      it again.  */
 457   if (DONT_SIMULATE_AGAIN (phi))
 458     return;
 459
 460   if (dump_file && (dump_flags & TDF_DETAILS))
 461     {
 462       fprintf (dump_file, "\nVisiting PHI node: ");
 463       print_generic_expr (dump_file, phi, dump_flags);
 464     }
 465
 466   curr_val = get_value (PHI_RESULT (phi));
 467   switch (curr_val->lattice_val)
 468     {
 469     case VARYING:
 470       if (dump_file && (dump_flags & TDF_DETAILS))
 471         fprintf (dump_file, "\n   Shortcircuit. Default of VARYING.");
 472       short_circuit = 1;
 473       break;
 474
 475     case CONSTANT:
 476       phi_val = *curr_val;
 477       break;
 478
 479     case UNDEFINED:
 480     case UNINITIALIZED:
 481       phi_val.lattice_val = UNDEFINED;
 482       phi_val.const_val = NULL_TREE;
 483       break;
 484
 485     default:
 486       abort ();
 487     }
 488
 489   /* If the variable is volatile or the variable is never referenced in a
 490      real operand, then consider the PHI node VARYING.  */
 491   if (short_circuit || TREE_THIS_VOLATILE (SSA_NAME_VAR (PHI_RESULT (phi))))
 492     {
 493       phi_val.lattice_val = VARYING;
 494       phi_val.const_val = NULL;
 495     }
 496   else
 497     for (i = 0; i < PHI_NUM_ARGS (phi); i++)
 498       {
 499         /* Compute the meet operator over all the PHI arguments.  */
 500         edge e = PHI_ARG_EDGE (phi, i);
 501
 502         if (dump_file && (dump_flags & TDF_DETAILS))
 503           {
 504             fprintf (dump_file,
 505                      "\n    Argument #%d (%d -> %d %sexecutable)\n",
 506                      i, e->src->index, e->dest->index,
 507                      (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
 508           }
 509
 510         /* If the incoming edge is executable, Compute the meet operator for
 511            the existing value of the PHI node and the current PHI argument.  */
 512         if (e->flags & EDGE_EXECUTABLE)
 513           {
 514             tree rdef = PHI_ARG_DEF (phi, i);
 515             value *rdef_val, val;
 516
 517             if (is_gimple_min_invariant (rdef))
 518               {
 519                 val.lattice_val = CONSTANT;
 520                 val.const_val = rdef;
 521                 rdef_val = &val;
 522               }
 523             else
 524               rdef_val = get_value (rdef);
 525
 526             phi_val = cp_lattice_meet (phi_val, *rdef_val);
 527
 528             if (dump_file && (dump_flags & TDF_DETAILS))
 529               {
 530                 fprintf (dump_file, "\t");
 531                 print_generic_expr (dump_file, rdef, dump_flags);
 532                 dump_lattice_value (dump_file, "\tValue: ", *rdef_val);
 533                 fprintf (dump_file, "\n");
 534               }
 535
 536             if (phi_val.lattice_val == VARYING)
 537               break;
 538           }
 539       }
 540
 541   if (dump_file && (dump_flags & TDF_DETAILS))
 542     {
 543       dump_lattice_value (dump_file, "\n    PHI node value: ", phi_val);
 544       fprintf (dump_file, "\n\n");
 545     }
 546
 547   set_lattice_value (PHI_RESULT (phi), phi_val);
 548   if (phi_val.lattice_val == VARYING)
 549     DONT_SIMULATE_AGAIN (phi) = 1;
 550 }
 551
 552
 553 /* Compute the meet operator between VAL1 and VAL2:
 554
 555                 any M UNDEFINED = any
 556                 any M VARYING   = VARYING
 557                 Ci  M Cj        = Ci            if (i == j)
 558                 Ci  M Cj        = VARYING       if (i != j)  */
 559 static value
 560 cp_lattice_meet (value val1, value val2)
 561 {
 562   value result;
 563
 564   /* any M UNDEFINED = any.  */
 565   if (val1.lattice_val == UNDEFINED)
 566     return val2;
 567   else if (val2.lattice_val == UNDEFINED)
 568     return val1;
 569
 570   /* any M VARYING = VARYING.  */
 571   if (val1.lattice_val == VARYING || val2.lattice_val == VARYING)
 572     {
 573       result.lattice_val = VARYING;
 574       result.const_val = NULL_TREE;
 575       return result;
 576     }
 577
 578   /* Ci M Cj = Ci       if (i == j)
 579      Ci M Cj = VARYING  if (i != j)  */
 580   if (simple_cst_equal (val1.const_val, val2.const_val) == 1)
 581     {
 582       result.lattice_val = CONSTANT;
 583       result.const_val = val1.const_val;
 584     }
 585   else
 586     {
 587       result.lattice_val = VARYING;
 588       result.const_val = NULL_TREE;
 589     }
 590
 591   return result;
 592 }
 593
 594
 595 /* Evaluate statement STMT.  If the statement produces an output value and
 596    its evaluation changes the lattice value of its output, do the following:
 597
 598    - If the statement is an assignment, add all the SSA edges starting at
 599      this definition.
 600
 601    - If the statement is a conditional branch:
 602         . If the statement evaluates to non-constant, add all edges to
 603           worklist.
 604         . If the statement is constant, add the edge executed as the
 605           result of the branch.  */
 606
 607 static void
 608 visit_stmt (tree stmt)
 609 {
 610   size_t i;
 611   stmt_ann_t ann;
 612   def_optype defs;
 613   v_may_def_optype v_may_defs;
 614   v_must_def_optype v_must_defs;
 615
 616   /* If the statement has already been deemed to be VARYING, don't simulate
 617      it again.  */
 618   if (DONT_SIMULATE_AGAIN (stmt))
 619     return;
 620
 621   if (dump_file && (dump_flags & TDF_DETAILS))
 622     {
 623       fprintf (dump_file, "\nVisiting statement: ");
 624       print_generic_stmt (dump_file, stmt, TDF_SLIM);
 625       fprintf (dump_file, "\n");
 626     }
 627
 628   ann = stmt_ann (stmt);
 629
 630   /* If this statement is already in the worklist then "cancel" it.  The
 631      reevaluation implied by the worklist entry will produce the same
 632      value we generate here and thus reevaluating it again from the
 633      worklist is pointless.  */
 634   if (ann->in_ccp_worklist)
 635     ann->in_ccp_worklist = 0;
 636
 637   /* Now examine the statement.  If the statement is an assignment that
 638      produces a single output value, evaluate its RHS to see if the lattice
 639      value of its output has changed.  */
 640   if (TREE_CODE (stmt) == MODIFY_EXPR
 641       && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME)
 642     visit_assignment (stmt);
 643
 644   /* Definitions made by statements other than assignments to SSA_NAMEs
 645      represent unknown modifications to their outputs.  Mark them VARYING.  */
 646   else if (NUM_DEFS (defs = DEF_OPS (ann)) != 0)
 647     {
 648       DONT_SIMULATE_AGAIN (stmt) = 1;
 649       for (i = 0; i < NUM_DEFS (defs); i++)
 650         {
 651           tree def = DEF_OP (defs, i);
 652           def_to_varying (def);
 653         }
 654     }
 655
 656   /* If STMT is a conditional branch, see if we can determine which branch
 657      will be taken.  */
 658   else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
 659     visit_cond_stmt (stmt);
 660
 661   /* Any other kind of statement is not interesting for constant
 662      propagation and, therefore, not worth simulating.  */
 663   else
 664     {
 665       DONT_SIMULATE_AGAIN (stmt) = 1;
 666
 667       /* If STMT is a computed goto, then mark all the output edges
 668          executable.  */
 669       if (computed_goto_p (stmt))
 670         add_outgoing_control_edges (bb_for_stmt (stmt));
 671     }
 672
 673   /* Mark all V_MAY_DEF operands VARYING.  */
 674   v_may_defs = V_MAY_DEF_OPS (ann);
 675   for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
 676     def_to_varying (V_MAY_DEF_RESULT (v_may_defs, i));
 677
 678   /* Mark all V_MUST_DEF operands VARYING.  */
 679   v_must_defs = V_MUST_DEF_OPS (ann);
 680   for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
 681     def_to_varying (V_MUST_DEF_OP (v_must_defs, i));
 682 }
 683
 684
 685 /* Visit the assignment statement STMT.  Set the value of its LHS to the
 686    value computed by the RHS.  */
 687
 688 static void
 689 visit_assignment (tree stmt)
 690 {
 691   value val;
 692   tree lhs, rhs;
 693
 694   lhs = TREE_OPERAND (stmt, 0);
 695   rhs = TREE_OPERAND (stmt, 1);
 696
 697   if (TREE_THIS_VOLATILE (SSA_NAME_VAR (lhs)))
 698     {
 699       /* Volatile variables are always VARYING.  */
 700       val.lattice_val = VARYING;
 701       val.const_val = NULL_TREE;
 702     }
 703   else if (TREE_CODE (rhs) == SSA_NAME)
 704     {
 705       /* For a simple copy operation, we copy the lattice values.  */
 706       value *nval = get_value (rhs);
 707       val = *nval;
 708     }
 709   else
 710     {
 711       /* Evaluate the statement.  */
 712       val = evaluate_stmt (stmt);
 713     }
 714
 715   /* FIXME: Hack.  If this was a definition of a bitfield, we need to widen
 716      the constant value into the type of the destination variable.  This
 717      should not be necessary if GCC represented bitfields properly.  */
 718   {
 719     tree lhs = TREE_OPERAND (stmt, 0);
 720     if (val.lattice_val == CONSTANT
 721         && TREE_CODE (lhs) == COMPONENT_REF
 722         && DECL_BIT_FIELD (TREE_OPERAND (lhs, 1)))
 723       {
 724         tree w = widen_bitfield (val.const_val, TREE_OPERAND (lhs, 1), lhs);
 725
 726         if (w && is_gimple_min_invariant (w))
 727           val.const_val = w;
 728         else
 729           {
 730             val.lattice_val = VARYING;
 731             val.const_val = NULL;
 732           }
 733       }
 734   }
 735
 736   /* Set the lattice value of the statement's output.  */
 737   set_lattice_value (lhs, val);
 738   if (val.lattice_val == VARYING)
 739     DONT_SIMULATE_AGAIN (stmt) = 1;
 740 }
 741
 742
 743 /* Visit the conditional statement STMT.  If it evaluates to a constant value,
 744    mark outgoing edges appropriately.  */
 745
 746 static void
 747 visit_cond_stmt (tree stmt)
 748 {
 749   edge e;
 750   value val;
 751   basic_block block;
 752
 753   block = bb_for_stmt (stmt);
 754   val = evaluate_stmt (stmt);
 755
 756   /* Find which edge out of the conditional block will be taken and add it
 757      to the worklist.  If no single edge can be determined statically, add
 758      all outgoing edges from BLOCK.  */
 759   e = find_taken_edge (block, val.const_val);
 760   if (e)
 761     add_control_edge (e);
 762   else
 763     {
 764       DONT_SIMULATE_AGAIN (stmt) = 1;
 765       add_outgoing_control_edges (block);
 766     }
 767 }
 768
 769
 770 /* Add all the edges coming out of BB to the control flow worklist.  */
 771
 772 static void
 773 add_outgoing_control_edges (basic_block bb)
 774 {
 775   edge e;
 776
 777   for (e = bb->succ; e; e = e->succ_next)
 778     add_control_edge (e);
 779 }
 780
 781
 782 /* Add edge E to the control flow worklist.  */
 783
 784 static void
 785 add_control_edge (edge e)
 786 {
 787   basic_block bb = e->dest;
 788   if (bb == EXIT_BLOCK_PTR)
 789     return;
 790
 791   /* If the edge had already been executed, skip it.  */
 792   if (e->flags & EDGE_EXECUTABLE)
 793       return;
 794
 795   e->flags |= EDGE_EXECUTABLE;
 796
 797   /* If the block is already in the list, we're done.  */
 798   if (TEST_BIT (bb_in_list, bb->index))
 799     return;
 800
 801   cfg_blocks_add (bb);
 802
 803   if (dump_file && (dump_flags & TDF_DETAILS))
 804     fprintf (dump_file, "Adding Destination of edge (%d -> %d) to worklist\n\n",
 805              e->src->index, e->dest->index);
 806 }
 807
 808
 809 /* CCP specific front-end to the non-destructive constant folding routines.
 810
 811    Attempt to simplify the RHS of STMT knowing that one or more
 812    operands are constants.
 813
 814    If simplification is possible, return the simplified RHS,
 815    otherwise return the original RHS.  */
 816
 817 static tree
 818 ccp_fold (tree stmt)
 819 {
 820   tree rhs = get_rhs (stmt);
 821   enum tree_code code = TREE_CODE (rhs);
 822   int kind = TREE_CODE_CLASS (code);
 823   tree retval = NULL_TREE;
 824
 825   /* If the RHS is just a variable, then that variable must now have
 826      a constant value that we can return directly.  */
 827   if (TREE_CODE (rhs) == SSA_NAME)
 828     return get_value (rhs)->const_val;
 829
 830   /* Unary operators.  Note that we know the single operand must
 831      be a constant.  So this should almost always return a
 832      simplified RHS.  */
 833   if (kind == '1')
 834     {
 835       /* Handle unary operators which can appear in GIMPLE form.  */
 836       tree op0 = TREE_OPERAND (rhs, 0);
 837
 838       /* Simplify the operand down to a constant.  */
 839       if (TREE_CODE (op0) == SSA_NAME)
 840         {
 841           value *val = get_value (op0);
 842           if (val->lattice_val == CONSTANT)
 843             op0 = get_value (op0)->const_val;
 844         }
 845
 846       retval = nondestructive_fold_unary_to_constant (code,
 847                                                       TREE_TYPE (rhs),
 848                                                       op0);
 849
 850       /* If we folded, but did not create an invariant, then we can not
 851          use this expression.  */
 852       if (retval && ! is_gimple_min_invariant (retval))
 853         return NULL;
 854
 855       /* If we could not fold the expression, but the arguments are all
 856          constants and gimple values, then build and return the new
 857          expression.
 858
 859          In some cases the new expression is still something we can
 860          use as a replacement for an argument.  This happens with
 861          NOP conversions of types for example.
 862
 863          In other cases the new expression can not be used as a
 864          replacement for an argument (as it would create non-gimple
 865          code).  But the new expression can still be used to derive
 866          other constants.  */
 867       if (! retval && is_gimple_min_invariant (op0))
 868         return build1 (code, TREE_TYPE (rhs), op0);
 869     }
 870
 871   /* Binary and comparison operators.  We know one or both of the
 872      operands are constants.  */
 873   else if (kind == '2'
 874            || kind == '<'
 875            || code == TRUTH_AND_EXPR
 876            || code == TRUTH_OR_EXPR
 877            || code == TRUTH_XOR_EXPR)
 878     {
 879       /* Handle binary and comparison operators that can appear in
 880          GIMPLE form.  */
 881       tree op0 = TREE_OPERAND (rhs, 0);
 882       tree op1 = TREE_OPERAND (rhs, 1);
 883
 884       /* Simplify the operands down to constants when appropriate.  */
 885       if (TREE_CODE (op0) == SSA_NAME)
 886         {
 887           value *val = get_value (op0);
 888           if (val->lattice_val == CONSTANT)
 889             op0 = val->const_val;
 890         }
 891
 892       if (TREE_CODE (op1) == SSA_NAME)
 893         {
 894           value *val = get_value (op1);
 895           if (val->lattice_val == CONSTANT)
 896             op1 = val->const_val;
 897         }
 898
 899       retval = nondestructive_fold_binary_to_constant (code,
 900                                                        TREE_TYPE (rhs),
 901                                                        op0, op1);
 902
 903       /* If we folded, but did not create an invariant, then we can not
 904          use this expression.  */
 905       if (retval && ! is_gimple_min_invariant (retval))
 906         return NULL;
 907
 908       /* If we could not fold the expression, but the arguments are all
 909          constants and gimple values, then build and return the new
 910          expression.
 911
 912          In some cases the new expression is still something we can
 913          use as a replacement for an argument.  This happens with
 914          NOP conversions of types for example.
 915
 916          In other cases the new expression can not be used as a
 917          replacement for an argument (as it would create non-gimple
 918          code).  But the new expression can still be used to derive
 919          other constants.  */
 920       if (! retval
 921           && is_gimple_min_invariant (op0)
 922           && is_gimple_min_invariant (op1))
 923         return build (code, TREE_TYPE (rhs), op0, op1);
 924     }
 925
 926   /* We may be able to fold away calls to builtin functions if their
 927      arguments are constants.  */
 928   else if (code == CALL_EXPR
 929            && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR
 930            && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))
 931                == FUNCTION_DECL)
 932            && DECL_BUILT_IN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)))
 933     {
 934       use_optype uses = STMT_USE_OPS (stmt);
 935       if (NUM_USES (uses) != 0)
 936         {
 937           tree *orig;
 938           size_t i;
 939
 940           /* Preserve the original values of every operand.  */
 941           orig = xmalloc (sizeof (tree) * NUM_USES (uses));
 942           for (i = 0; i < NUM_USES (uses); i++)
 943             orig[i] = USE_OP (uses, i);
 944
 945           /* Substitute operands with their values and try to fold.  */
 946           replace_uses_in (stmt, NULL);
 947           retval = fold_builtin (rhs);
 948
 949           /* Restore operands to their original form.  */
 950           for (i = 0; i < NUM_USES (uses); i++)
 951             *(USE_OP_PTR (uses, i)) = orig[i];
 952           free (orig);
 953         }
 954     }
 955   else
 956     return rhs;
 957
 958   /* If we got a simplified form, see if we need to convert its type.  */
 959   if (retval)
 960     {
 961       if (TREE_TYPE (retval) != TREE_TYPE (rhs))
 962         retval = fold_convert (TREE_TYPE (rhs), retval);
 963
 964       if (TREE_TYPE (retval) == TREE_TYPE (rhs))
 965         return retval;
 966     }
 967
 968   /* No simplification was possible.  */
 969   return rhs;
 970 }
 971
 972
 973 /* Evaluate statement STMT.  */
 974
 975 static value
 976 evaluate_stmt (tree stmt)
 977 {
 978   value val;
 979   tree simplified;
 980   latticevalue likelyvalue = likely_value (stmt);
 981
 982   /* If the statement is likely to have a CONSTANT result, then try
 983      to fold the statement to determine the constant value.  */
 984   if (likelyvalue == CONSTANT)
 985     simplified = ccp_fold (stmt);
 986   /* If the statement is likely to have a VARYING result, then do not
 987      bother folding the statement.  */
 988   else if (likelyvalue == VARYING)
 989     simplified = get_rhs (stmt);
 990   /* Otherwise the statement is likely to have an UNDEFINED value and
 991      there will be nothing to do.  */
 992   else
 993     simplified = NULL_TREE;
 994
 995   if (simplified && is_gimple_min_invariant (simplified))
 996     {
 997       /* The statement produced a constant value.  */
 998       val.lattice_val = CONSTANT;
 999       val.const_val = simplified;
1000     }
1001   else
1002     {
1003       /* The statement produced a nonconstant value.  If the statement
1004          had undefined operands, then the result of the statement should
1005          be undefined.  Else the result of the statement is VARYING.  */
1006       val.lattice_val = (likelyvalue == UNDEFINED ? UNDEFINED : VARYING);
1007       val.const_val = NULL_TREE;
1008     }
1009
1010   return val;
1011 }
1012
1013
1014 /* Debugging dumps.  */
1015
1016 static void
1017 dump_lattice_value (FILE *outf, const char *prefix, value val)
1018 {
1019   switch (val.lattice_val)
1020     {
1021     case UNDEFINED:
1022       fprintf (outf, "%sUNDEFINED", prefix);
1023       break;
1024     case VARYING:
1025       fprintf (outf, "%sVARYING", prefix);
1026       break;
1027     case CONSTANT:
1028       fprintf (outf, "%sCONSTANT ", prefix);
1029       print_generic_expr (outf, val.const_val, dump_flags);
1030       break;
1031     default:
1032       abort ();
1033     }
1034 }
1035
1036 /* Given a constant value VAL for bitfield FIELD, and a destination
1037    variable VAR, return VAL appropriately widened to fit into VAR.  If
1038    FIELD is wider than HOST_WIDE_INT, NULL is returned.  */
1039
1040 tree
1041 widen_bitfield (tree val, tree field, tree var)
1042 {
1043   unsigned var_size, field_size;
1044   tree wide_val;
1045   unsigned HOST_WIDE_INT mask;
1046   unsigned i;
1047
1048   var_size = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE ((var))));
1049   field_size = TREE_INT_CST_LOW (DECL_SIZE (field));
1050
1051   /* Give up if either the bitfield or the variable are too wide.  */
1052   if (field_size > HOST_BITS_PER_WIDE_INT || var_size > HOST_BITS_PER_WIDE_INT)
1053     return NULL;
1054
1055 #if defined ENABLE_CHECKING
1056   if (var_size < field_size)
1057     abort ();
1058 #endif
1059
1060   /* If VAL is not an integer constant, then give up.  */
1061   if (TREE_CODE (val) != INTEGER_CST)
1062     return NULL;
1063
1064   /* If the sign bit of the value is not set, or the field's type is
1065      unsigned, then just mask off the high order bits of the value.  */
1066   if ((TREE_INT_CST_LOW (val) & (1 << (field_size - 1))) == 0
1067       || DECL_UNSIGNED (field))
1068     {
1069       /* Zero extension.  Build a mask with the lower 'field_size' bits
1070          set and a BIT_AND_EXPR node to clear the high order bits of
1071          the value.  */
1072       for (i = 0, mask = 0; i < field_size; i++)
1073         mask |= 1 << i;
1074
1075       wide_val = build (BIT_AND_EXPR, TREE_TYPE (var), val,
1076                         build_int_2 (mask, 0));
1077     }
1078   else
1079     {
1080       /* Sign extension.  Create a mask with the upper 'field_size'
1081          bits set and a BIT_IOR_EXPR to set the high order bits of the
1082          value.  */
1083       for (i = 0, mask = 0; i < (var_size - field_size); i++)
1084         mask |= 1 << (var_size - i - 1);
1085
1086       wide_val = build (BIT_IOR_EXPR, TREE_TYPE (var), val,
1087                         build_int_2 (mask, 0));
1088     }
1089
1090   return fold (wide_val);
1091 }
1092
1093
1094 /* Function indicating whether we ought to include information for 'var'
1095    when calculating immediate uses.  */
1096
1097 static bool
1098 need_imm_uses_for (tree var)
1099 {
1100   return get_value (var)->lattice_val != VARYING;
1101 }
1102
1103
1104 /* Initialize local data structures and worklists for CCP.  */
1105
1106 static void
1107 initialize (void)
1108 {
1109   edge e;
1110   basic_block bb;
1111   sbitmap virtual_var;
1112
1113   /* Worklists of SSA edges.  */
1114   VARRAY_TREE_INIT (ssa_edges, 20, "ssa_edges");
1115   VARRAY_TREE_INIT (varying_ssa_edges, 20, "varying_ssa_edges");
1116
1117   executable_blocks = sbitmap_alloc (last_basic_block);
1118   sbitmap_zero (executable_blocks);
1119
1120   bb_in_list = sbitmap_alloc (last_basic_block);
1121   sbitmap_zero (bb_in_list);
1122
1123   value_vector = (value *) xmalloc (num_ssa_names * sizeof (value));
1124   memset (value_vector, 0, num_ssa_names * sizeof (value));
1125
1126   /* 1 if ssa variable is used in a virtual variable context.  */
1127   virtual_var = sbitmap_alloc (num_ssa_names);
1128   sbitmap_zero (virtual_var);
1129
1130   /* Initialize default values and simulation flags for PHI nodes, statements
1131      and edges.  */
1132   FOR_EACH_BB (bb)
1133     {
1134       block_stmt_iterator i;
1135       tree stmt;
1136       stmt_ann_t ann;
1137       def_optype defs;
1138       v_may_def_optype v_may_defs;
1139       v_must_def_optype v_must_defs;
1140       size_t x;
1141       int vary;
1142
1143       /* Get the default value for each definition.  */
1144       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
1145         {
1146           vary = 0;
1147           stmt = bsi_stmt (i);
1148           get_stmt_operands (stmt);
1149           ann = stmt_ann (stmt);
1150           defs = DEF_OPS (ann);
1151           for (x = 0; x < NUM_DEFS (defs); x++)
1152             {
1153               tree def = DEF_OP (defs, x);
1154               if (get_value (def)->lattice_val == VARYING)
1155                 vary = 1;
1156             }
1157           DONT_SIMULATE_AGAIN (stmt) = vary;
1158
1159           /* Mark all V_MAY_DEF operands VARYING.  */
1160           v_may_defs = V_MAY_DEF_OPS (ann);
1161           for (x = 0; x < NUM_V_MAY_DEFS (v_may_defs); x++)
1162             {
1163               tree res = V_MAY_DEF_RESULT (v_may_defs, x);
1164               get_value (res)->lattice_val = VARYING;
1165               SET_BIT (virtual_var, SSA_NAME_VERSION (res));
1166             }
1167
1168           /* Mark all V_MUST_DEF operands VARYING.  */
1169           v_must_defs = V_MUST_DEF_OPS (ann);
1170           for (x = 0; x < NUM_V_MUST_DEFS (v_must_defs); x++)
1171             {
1172               tree v_must_def = V_MUST_DEF_OP (v_must_defs, x);
1173               get_value (v_must_def)->lattice_val = VARYING;
1174               SET_BIT (virtual_var, SSA_NAME_VERSION (v_must_def));
1175             }
1176         }
1177
1178       for (e = bb->succ; e; e = e->succ_next)
1179         e->flags &= ~EDGE_EXECUTABLE;
1180     }
1181
1182   /* Now process PHI nodes.  */
1183   FOR_EACH_BB (bb)
1184     {
1185       tree phi, var;
1186       int x;
1187       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1188         {
1189           value *val;
1190           val = get_value (PHI_RESULT (phi));
1191           if (val->lattice_val != VARYING)
1192             {
1193               for (x = 0; x < PHI_NUM_ARGS (phi); x++)
1194                 {
1195                   var = PHI_ARG_DEF (phi, x);
1196                   /* If one argument is virtual, the result is virtual, and
1197                      therefore varying.  */
1198                   if (TREE_CODE (var) == SSA_NAME)
1199                     {
1200                       if (TEST_BIT (virtual_var, SSA_NAME_VERSION (var)))
1201                         {
1202                           val->lattice_val = VARYING;
1203                           SET_BIT (virtual_var,
1204                                    SSA_NAME_VERSION (PHI_RESULT (phi)));
1205                           break;
1206                         }
1207                     }
1208         }
1209             }
1210           DONT_SIMULATE_AGAIN (phi) = ((val->lattice_val == VARYING) ? 1 : 0);
1211         }
1212     }
1213
1214   sbitmap_free (virtual_var);
1215   /* Compute immediate uses for variables we care about.  */
1216   compute_immediate_uses (TDFA_USE_OPS, need_imm_uses_for);
1217
1218   if (dump_file && (dump_flags & TDF_DETAILS))
1219     dump_immediate_uses (dump_file);
1220
1221   VARRAY_BB_INIT (cfg_blocks, 20, "cfg_blocks");
1222
1223   /* Seed the algorithm by adding the successors of the entry block to the
1224      edge worklist.  */
1225   for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
1226     {
1227       if (e->dest != EXIT_BLOCK_PTR)
1228         {
1229           e->flags |= EDGE_EXECUTABLE;
1230           cfg_blocks_add (e->dest);
1231         }
1232     }
1233 }
1234
1235
1236 /* Free allocated storage.  */
1237
1238 static void
1239 finalize (void)
1240 {
1241   ssa_edges = NULL;
1242   varying_ssa_edges = NULL;
1243   cfg_blocks = NULL;
1244   free (value_vector);
1245   sbitmap_free (bb_in_list);
1246   sbitmap_free (executable_blocks);
1247   free_df ();
1248 }
1249
1250 /* Is the block worklist empty.  */
1251
1252 static inline bool
1253 cfg_blocks_empty_p (void)
1254 {
1255   return (cfg_blocks_num == 0);
1256 }
1257
1258 /* Add a basic block to the worklist.  */
1259
1260 static void
1261 cfg_blocks_add (basic_block bb)
1262 {
1263    if (bb == ENTRY_BLOCK_PTR || bb == EXIT_BLOCK_PTR)
1264      return;
1265
1266    if (TEST_BIT (bb_in_list, bb->index))
1267      return;
1268
1269     if (cfg_blocks_empty_p ())
1270       {
1271         cfg_blocks_tail = cfg_blocks_head = 0;
1272         cfg_blocks_num = 1;
1273       }
1274     else
1275       {
1276         cfg_blocks_num++;
1277         if (cfg_blocks_num > VARRAY_SIZE (cfg_blocks))
1278           {
1279             /* We have to grow the array now.  Adjust to queue to occupy the
1280                full space of the original array.  */
1281             cfg_blocks_tail = VARRAY_SIZE (cfg_blocks);
1282             cfg_blocks_head = 0;
1283             VARRAY_GROW (cfg_blocks, 2 * VARRAY_SIZE (cfg_blocks));
1284           }
1285         else
1286           cfg_blocks_tail = (cfg_blocks_tail + 1) % VARRAY_SIZE (cfg_blocks);
1287       }
1288     VARRAY_BB (cfg_blocks, cfg_blocks_tail) = bb;
1289     SET_BIT (bb_in_list, bb->index);
1290 }
1291
1292 /* Remove a block from the worklist.  */
1293
1294 static basic_block
1295 cfg_blocks_get (void)
1296 {
1297   basic_block bb;
1298
1299   bb = VARRAY_BB (cfg_blocks, cfg_blocks_head);
1300
1301 #ifdef ENABLE_CHECKING
1302   if (cfg_blocks_empty_p () || !bb)
1303     abort ();
1304 #endif
1305
1306   cfg_blocks_head = (cfg_blocks_head + 1) % VARRAY_SIZE (cfg_blocks);
1307   --cfg_blocks_num;
1308   RESET_BIT (bb_in_list, bb->index);
1309
1310   return bb;
1311 }
1312
1313 /* We have just defined a new value for VAR.  Add all immediate uses
1314    of VAR to the ssa_edges or varying_ssa_edges worklist.  */
1315 static void
1316 add_var_to_ssa_edges_worklist (tree var, value val)
1317 {
1318   tree stmt = SSA_NAME_DEF_STMT (var);
1319   dataflow_t df = get_immediate_uses (stmt);
1320   int num_uses = num_immediate_uses (df);
1321   int i;
1322
1323   for (i = 0; i < num_uses; i++)
1324     {
1325       tree use = immediate_use (df, i);
1326
1327       if (!DONT_SIMULATE_AGAIN (use))
1328         {
1329           stmt_ann_t ann = stmt_ann (use);
1330           if (ann->in_ccp_worklist == 0)
1331             {
1332               ann->in_ccp_worklist = 1;
1333               if (val.lattice_val == VARYING)
1334                 VARRAY_PUSH_TREE (varying_ssa_edges, use);
1335               else
1336                 VARRAY_PUSH_TREE (ssa_edges, use);
1337             }
1338         }
1339     }
1340 }
1341
1342 /* Set the lattice value for the variable VAR to VARYING.  */
1343
1344 static void
1345 def_to_varying (tree var)
1346 {
1347   value val;
1348   val.lattice_val = VARYING;
1349   val.const_val = NULL_TREE;
1350   set_lattice_value (var, val);
1351 }
1352
1353 /* Set the lattice value for variable VAR to VAL.  */
1354
1355 static void
1356 set_lattice_value (tree var, value val)
1357 {
1358   value *old = get_value (var);
1359
1360 #ifdef ENABLE_CHECKING
1361   if (val.lattice_val == UNDEFINED)
1362     {
1363       /* CONSTANT->UNDEFINED is never a valid state transition.  */
1364       if (old->lattice_val == CONSTANT)
1365         abort ();
1366
1367       /* VARYING->UNDEFINED is generally not a valid state transition,
1368          except for values which are initialized to VARYING.  */
1369       if (old->lattice_val == VARYING
1370           && get_default_value (var).lattice_val != VARYING)
1371         abort ();
1372     }
1373   else if (val.lattice_val == CONSTANT)
1374     {
1375       /* VARYING -> CONSTANT is an invalid state transition, except
1376          for objects which start off in a VARYING state.  */
1377       if (old->lattice_val == VARYING
1378           && get_default_value (var).lattice_val != VARYING)
1379         abort ();
1380     }
1381 #endif
1382
1383   /* If the constant for VAR has changed, then this VAR is really varying.  */
1384   if (old->lattice_val == CONSTANT && val.lattice_val == CONSTANT
1385       && !simple_cst_equal (old->const_val, val.const_val))
1386     {
1387       val.lattice_val = VARYING;
1388       val.const_val = NULL_TREE;
1389     }
1390
1391   if (old->lattice_val != val.lattice_val)
1392     {
1393       if (dump_file && (dump_flags & TDF_DETAILS))
1394         {
1395           dump_lattice_value (dump_file,
1396                               "Lattice value changed to ", val);
1397           fprintf (dump_file, ".  Adding definition to SSA edges.\n");
1398         }
1399
1400       add_var_to_ssa_edges_worklist (var, val);
1401       *old = val;
1402     }
1403 }
1404
1405 /* Replace USE references in statement STMT with their immediate reaching
1406    definition.  Return true if at least one reference was replaced.  If
1407    REPLACED_ADDRESSES_P is given, it will be set to true if an address
1408    constant was replaced.  */
1409
1410 static bool
1411 replace_uses_in (tree stmt, bool *replaced_addresses_p)
1412 {
1413   bool replaced = false;
1414   use_optype uses;
1415   size_t i;
1416
1417   if (replaced_addresses_p)
1418     *replaced_addresses_p = false;
1419
1420   get_stmt_operands (stmt);
1421
1422   uses = STMT_USE_OPS (stmt);
1423   for (i = 0; i < NUM_USES (uses); i++)
1424     {
1425       tree *use = USE_OP_PTR (uses, i);
1426       value *val = get_value (*use);
1427
1428       if (val->lattice_val == CONSTANT)
1429         {
1430           *use = val->const_val;
1431           replaced = true;
1432           if (POINTER_TYPE_P (TREE_TYPE (*use)) && replaced_addresses_p)
1433             *replaced_addresses_p = true;
1434         }
1435     }
1436
1437   return replaced;
1438 }
1439
1440 /* Return the likely latticevalue for STMT.
1441
1442    If STMT has no operands, then return CONSTANT.
1443
1444    Else if any operands of STMT are undefined, then return UNDEFINED.
1445
1446    Else if any operands of STMT are constants, then return CONSTANT.
1447
1448    Else return VARYING.  */
1449
1450 static latticevalue
1451 likely_value (tree stmt)
1452 {
1453   use_optype uses;
1454   size_t i;
1455   int found_constant = 0;
1456   stmt_ann_t ann;
1457
1458   /* If the statement makes aliased loads or has volatile operands, it
1459      won't fold to a constant value.  */
1460   ann = stmt_ann (stmt);
1461   if (ann->makes_aliased_loads || ann->has_volatile_ops)
1462     return VARYING;
1463
1464   /* A CALL_EXPR is assumed to be varying.  This may be overly conservative,
1465      in the presence of const and pure calls.  */
1466   if (get_call_expr_in (stmt) != NULL_TREE)
1467     return VARYING;
1468
1469   get_stmt_operands (stmt);
1470
1471   uses = USE_OPS (ann);
1472   for (i = 0; i < NUM_USES (uses); i++)
1473     {
1474       tree use = USE_OP (uses, i);
1475       value *val = get_value (use);
1476
1477       if (val->lattice_val == UNDEFINED)
1478         return UNDEFINED;
1479
1480       if (val->lattice_val == CONSTANT)
1481         found_constant = 1;
1482     }
1483
1484   return ((found_constant || !uses) ? CONSTANT : VARYING);
1485 }
1486
1487 /* A subroutine of fold_stmt_r.  Attempts to fold *(A+O) to A[X].
1488    BASE is an array type.  OFFSET is a byte displacement.  ORIG_TYPE
1489    is the desired result type.  */
1490
1491 static tree
1492 maybe_fold_offset_to_array_ref (tree base, tree offset, tree orig_type)
1493 {
1494   unsigned HOST_WIDE_INT lquo, lrem;
1495   HOST_WIDE_INT hquo, hrem;
1496   tree elt_size, min_idx, idx;
1497   tree array_type, elt_type;
1498
1499   /* Ignore stupid user tricks of indexing non-array variables.  */
1500   array_type = TREE_TYPE (base);
1501   if (TREE_CODE (array_type) != ARRAY_TYPE)
1502     return NULL_TREE;
1503   elt_type = TREE_TYPE (array_type);
1504   if (!lang_hooks.types_compatible_p (orig_type, elt_type))
1505     return NULL_TREE;
1506
1507   /* Whee.  Ignore indexing of variable sized types.  */
1508   elt_size = TYPE_SIZE_UNIT (elt_type);
1509   if (TREE_CODE (elt_size) != INTEGER_CST)
1510     return NULL_TREE;
1511
1512   /* If the division isn't exact, then don't do anything.  Equally
1513      invalid as the above indexing of non-array variables.  */
1514   if (div_and_round_double (TRUNC_DIV_EXPR, 1,
1515                             TREE_INT_CST_LOW (offset),
1516                             TREE_INT_CST_HIGH (offset),
1517                             TREE_INT_CST_LOW (elt_size),
1518                             TREE_INT_CST_HIGH (elt_size),
1519                             &lquo, &hquo, &lrem, &hrem)
1520       || lrem || hrem)
1521     return NULL_TREE;
1522   idx = build_int_2_wide (lquo, hquo);
1523
1524   /* Re-bias the index by the min index of the array type.  */
1525   min_idx = TYPE_DOMAIN (TREE_TYPE (base));
1526   if (min_idx)
1527     {
1528       min_idx = TYPE_MIN_VALUE (min_idx);
1529       if (min_idx)
1530         {
1531           idx = convert (TREE_TYPE (min_idx), idx);
1532           if (!integer_zerop (min_idx))
1533             idx = int_const_binop (PLUS_EXPR, idx, min_idx, 1);
1534         }
1535     }
1536
1537   return build (ARRAY_REF, orig_type, base, idx);
1538 }
1539
1540 /* A subroutine of fold_stmt_r.  Attempts to fold *(S+O) to S.X.
1541    BASE is a record type.  OFFSET is a byte displacement.  ORIG_TYPE
1542    is the desired result type.  */
1543 /* ??? This doesn't handle class inheritance.  */
1544
1545 static tree
1546 maybe_fold_offset_to_component_ref (tree record_type, tree base, tree offset,
1547                                     tree orig_type, bool base_is_ptr)
1548 {
1549   tree f, t, field_type, tail_array_field;
1550
1551   if (TREE_CODE (record_type) != RECORD_TYPE
1552       && TREE_CODE (record_type) != UNION_TYPE
1553       && TREE_CODE (record_type) != QUAL_UNION_TYPE)
1554     return NULL_TREE;
1555
1556   /* Short-circuit silly cases.  */
1557   if (lang_hooks.types_compatible_p (record_type, orig_type))
1558     return NULL_TREE;
1559
1560   tail_array_field = NULL_TREE;
1561   for (f = TYPE_FIELDS (record_type); f ; f = TREE_CHAIN (f))
1562     {
1563       int cmp;
1564
1565       if (TREE_CODE (f) != FIELD_DECL)
1566         continue;
1567       if (DECL_BIT_FIELD (f))
1568         continue;
1569       if (TREE_CODE (DECL_FIELD_OFFSET (f)) != INTEGER_CST)
1570         continue;
1571
1572       /* ??? Java creates "interesting" fields for representing base classes.
1573          They have no name, and have no context.  With no context, we get into
1574          trouble with nonoverlapping_component_refs_p.  Skip them.  */
1575       if (!DECL_FIELD_CONTEXT (f))
1576         continue;
1577
1578       /* The previous array field isn't at the end.  */
1579       tail_array_field = NULL_TREE;
1580
1581       /* Check to see if this offset overlaps with the field.  */
1582       cmp = tree_int_cst_compare (DECL_FIELD_OFFSET (f), offset);
1583       if (cmp > 0)
1584         continue;
1585
1586       field_type = TREE_TYPE (f);
1587       if (cmp < 0)
1588         {
1589           /* Don't care about offsets into the middle of scalars.  */
1590           if (!AGGREGATE_TYPE_P (field_type))
1591             continue;
1592
1593           /* Check for array at the end of the struct.  This is often
1594              used as for flexible array members.  We should be able to
1595              turn this into an array access anyway.  */
1596           if (TREE_CODE (field_type) == ARRAY_TYPE)
1597             tail_array_field = f;
1598
1599           /* Check the end of the field against the offset.  */
1600           if (!DECL_SIZE_UNIT (f)
1601               || TREE_CODE (DECL_SIZE_UNIT (f)) != INTEGER_CST)
1602             continue;
1603           t = int_const_binop (MINUS_EXPR, offset, DECL_FIELD_OFFSET (f), 1);
1604           if (!tree_int_cst_lt (t, DECL_SIZE_UNIT (f)))
1605             continue;
1606
1607           /* If we matched, then set offset to the displacement into
1608              this field.  */
1609           offset = t;
1610         }
1611
1612       /* Here we exactly match the offset being checked.  If the types match,
1613          then we can return that field.  */
1614       else if (lang_hooks.types_compatible_p (orig_type, field_type))
1615         {
1616           if (base_is_ptr)
1617             base = build1 (INDIRECT_REF, record_type, base);
1618           t = build (COMPONENT_REF, field_type, base, f);
1619           return t;
1620         }
1621
1622       /* Don't care about type-punning of scalars.  */
1623       else if (!AGGREGATE_TYPE_P (field_type))
1624         return NULL_TREE;
1625
1626       goto found;
1627     }
1628
1629   if (!tail_array_field)
1630     return NULL_TREE;
1631
1632   f = tail_array_field;
1633   field_type = TREE_TYPE (f);
1634
1635  found:
1636   /* If we get here, we've got an aggregate field, and a possibly
1637      nonzero offset into them.  Recurse and hope for a valid match.  */
1638   if (base_is_ptr)
1639     base = build1 (INDIRECT_REF, record_type, base);
1640   base = build (COMPONENT_REF, field_type, base, f);
1641
1642   t = maybe_fold_offset_to_array_ref (base, offset, orig_type);
1643   if (t)
1644     return t;
1645   return maybe_fold_offset_to_component_ref (field_type, base, offset,
1646                                              orig_type, false);
1647 }
1648
1649 /* A subroutine of fold_stmt_r.  Attempt to simplify *(BASE+OFFSET).
1650    Return the simplified expression, or NULL if nothing could be done.  */
1651
1652 static tree
1653 maybe_fold_stmt_indirect (tree expr, tree base, tree offset)
1654 {
1655   tree t;
1656
1657   /* We may well have constructed a double-nested PLUS_EXPR via multiple
1658      substitutions.  Fold that down to one.  Remove NON_LVALUE_EXPRs that
1659      are sometimes added.  */
1660   base = fold (base);
1661   STRIP_NOPS (base);
1662   TREE_OPERAND (expr, 0) = base;
1663
1664   /* One possibility is that the address reduces to a string constant.  */
1665   t = fold_read_from_constant_string (expr);
1666   if (t)
1667     return t;
1668
1669   /* Add in any offset from a PLUS_EXPR.  */
1670   if (TREE_CODE (base) == PLUS_EXPR)
1671     {
1672       tree offset2;
1673
1674       offset2 = TREE_OPERAND (base, 1);
1675       if (TREE_CODE (offset2) != INTEGER_CST)
1676         return NULL_TREE;
1677       base = TREE_OPERAND (base, 0);
1678
1679       offset = int_const_binop (PLUS_EXPR, offset, offset2, 1);
1680     }
1681
1682   if (TREE_CODE (base) == ADDR_EXPR)
1683     {
1684       /* Strip the ADDR_EXPR.  */
1685       base = TREE_OPERAND (base, 0);
1686
1687       /* Try folding *(&B+O) to B[X].  */
1688       t = maybe_fold_offset_to_array_ref (base, offset, TREE_TYPE (expr));
1689       if (t)
1690         return t;
1691
1692       /* Try folding *(&B+O) to B.X.  */
1693       t = maybe_fold_offset_to_component_ref (TREE_TYPE (base), base, offset,
1694                                               TREE_TYPE (expr), false);
1695       if (t)
1696         return t;
1697
1698       /* Fold *&B to B.  */
1699       if (integer_zerop (offset))
1700         return base;
1701     }
1702   else
1703     {
1704       /* We can get here for out-of-range string constant accesses,
1705          such as "_"[3].  Bail out of the entire substitution search
1706          and arrange for the entire statement to be replaced by a
1707          call to __builtin_trap.  In all likelyhood this will all be
1708          constant-folded away, but in the meantime we can't leave with
1709          something that get_expr_operands can't understand.  */
1710
1711       t = base;
1712       STRIP_NOPS (t);
1713       if (TREE_CODE (t) == ADDR_EXPR
1714           && TREE_CODE (TREE_OPERAND (t, 0)) == STRING_CST)
1715         {
1716           /* FIXME: Except that this causes problems elsewhere with dead
1717              code not being deleted, and we abort in the rtl expanders
1718              because we failed to remove some ssa_name.  In the meantime,
1719              just return zero.  */
1720           /* FIXME2: This condition should be signaled by
1721              fold_read_from_constant_string directly, rather than
1722              re-checking for it here.  */
1723           return integer_zero_node;
1724         }
1725
1726       /* Try folding *(B+O) to B->X.  Still an improvement.  */
1727       if (POINTER_TYPE_P (TREE_TYPE (base)))
1728         {
1729           t = maybe_fold_offset_to_component_ref (TREE_TYPE (TREE_TYPE (base)),
1730                                                   base, offset,
1731                                                   TREE_TYPE (expr), true);
1732           if (t)
1733             return t;
1734         }
1735     }
1736
1737   /* Otherwise we had an offset that we could not simplify.  */
1738   return NULL_TREE;
1739 }
1740
1741 /* A subroutine of fold_stmt_r.  EXPR is a PLUS_EXPR.
1742
1743    A quaint feature extant in our address arithmetic is that there
1744    can be hidden type changes here.  The type of the result need
1745    not be the same as the type of the input pointer.
1746
1747    What we're after here is an expression of the form
1748         (T *)(&array + const)
1749    where the cast doesn't actually exist, but is implicit in the
1750    type of the PLUS_EXPR.  We'd like to turn this into
1751         &array[x]
1752    which may be able to propagate further.  */
1753
1754 static tree
1755 maybe_fold_stmt_addition (tree expr)
1756 {
1757   tree op0 = TREE_OPERAND (expr, 0);
1758   tree op1 = TREE_OPERAND (expr, 1);
1759   tree ptr_type = TREE_TYPE (expr);
1760   tree ptd_type;
1761   tree t;
1762   bool subtract = (TREE_CODE (expr) == MINUS_EXPR);
1763
1764   /* We're only interested in pointer arithmetic.  */
1765   if (!POINTER_TYPE_P (ptr_type))
1766     return NULL_TREE;
1767   /* Canonicalize the integral operand to op1.  */
1768   if (INTEGRAL_TYPE_P (TREE_TYPE (op0)))
1769     {
1770       if (subtract)
1771         return NULL_TREE;
1772       t = op0, op0 = op1, op1 = t;
1773     }
1774   /* It had better be a constant.  */
1775   if (TREE_CODE (op1) != INTEGER_CST)
1776     return NULL_TREE;
1777   /* The first operand should be an ADDR_EXPR.  */
1778   if (TREE_CODE (op0) != ADDR_EXPR)
1779     return NULL_TREE;
1780   op0 = TREE_OPERAND (op0, 0);
1781
1782   /* If the first operand is an ARRAY_REF, expand it so that we can fold
1783      the offset into it.  */
1784   while (TREE_CODE (op0) == ARRAY_REF)
1785     {
1786       tree array_obj = TREE_OPERAND (op0, 0);
1787       tree array_idx = TREE_OPERAND (op0, 1);
1788       tree elt_type = TREE_TYPE (op0);
1789       tree elt_size = TYPE_SIZE_UNIT (elt_type);
1790       tree min_idx;
1791
1792       if (TREE_CODE (array_idx) != INTEGER_CST)
1793         break;
1794       if (TREE_CODE (elt_size) != INTEGER_CST)
1795         break;
1796
1797       /* Un-bias the index by the min index of the array type.  */
1798       min_idx = TYPE_DOMAIN (TREE_TYPE (array_obj));
1799       if (min_idx)
1800         {
1801           min_idx = TYPE_MIN_VALUE (min_idx);
1802           if (min_idx)
1803             {
1804               array_idx = convert (TREE_TYPE (min_idx), array_idx);
1805               if (!integer_zerop (min_idx))
1806                 array_idx = int_const_binop (MINUS_EXPR, array_idx,
1807                                              min_idx, 0);
1808             }
1809         }
1810
1811       /* Convert the index to a byte offset.  */
1812       array_idx = convert (sizetype, array_idx);
1813       array_idx = int_const_binop (MULT_EXPR, array_idx, elt_size, 0);
1814
1815       /* Update the operands for the next round, or for folding.  */
1816       /* If we're manipulating unsigned types, then folding into negative
1817          values can produce incorrect results.  Particularly if the type
1818          is smaller than the width of the pointer.  */
1819       if (subtract
1820           && TYPE_UNSIGNED (TREE_TYPE (op1))
1821           && tree_int_cst_lt (array_idx, op1))
1822         return NULL;
1823       op1 = int_const_binop (subtract ? MINUS_EXPR : PLUS_EXPR,
1824                              array_idx, op1, 0);
1825       subtract = false;
1826       op0 = array_obj;
1827     }
1828
1829   /* If we weren't able to fold the subtraction into another array reference,
1830      canonicalize the integer for passing to the array and component ref
1831      simplification functions.  */
1832   if (subtract)
1833     {
1834       if (TYPE_UNSIGNED (TREE_TYPE (op1)))
1835         return NULL;
1836       op1 = fold (build1 (NEGATE_EXPR, TREE_TYPE (op1), op1));
1837       /* ??? In theory fold should always produce another integer.  */
1838       if (TREE_CODE (op1) != INTEGER_CST)
1839         return NULL;
1840     }
1841
1842   ptd_type = TREE_TYPE (ptr_type);
1843
1844   /* At which point we can try some of the same things as for indirects.  */
1845   t = maybe_fold_offset_to_array_ref (op0, op1, ptd_type);
1846   if (!t)
1847     t = maybe_fold_offset_to_component_ref (TREE_TYPE (op0), op0, op1,
1848                                             ptd_type, false);
1849   if (t)
1850     t = build1 (ADDR_EXPR, ptr_type, t);
1851
1852   return t;
1853 }
1854
1855 /* Subroutine of fold_stmt called via walk_tree.  We perform several
1856    simplifications of EXPR_P, mostly having to do with pointer arithmetic.  */
1857
1858 static tree
1859 fold_stmt_r (tree *expr_p, int *walk_subtrees, void *data)
1860 {
1861   bool *changed_p = data;
1862   tree expr = *expr_p, t;
1863
1864   /* ??? It'd be nice if walk_tree had a pre-order option.  */
1865   switch (TREE_CODE (expr))
1866     {
1867     case INDIRECT_REF:
1868       t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
1869       if (t)
1870         return t;
1871       *walk_subtrees = 0;
1872
1873       t = maybe_fold_stmt_indirect (expr, TREE_OPERAND (expr, 0),
1874                                     integer_zero_node);
1875       break;
1876
1877       /* ??? Could handle ARRAY_REF here, as a variant of INDIRECT_REF.
1878          We'd only want to bother decomposing an existing ARRAY_REF if
1879          the base array is found to have another offset contained within.
1880          Otherwise we'd be wasting time.  */
1881
1882     case ADDR_EXPR:
1883       t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
1884       if (t)
1885         return t;
1886       *walk_subtrees = 0;
1887
1888       /* Set TREE_INVARIANT properly so that the value is properly
1889          considered constant, and so gets propagated as expected.  */
1890       if (*changed_p)
1891         recompute_tree_invarant_for_addr_expr (expr);
1892       return NULL_TREE;
1893
1894     case PLUS_EXPR:
1895     case MINUS_EXPR:
1896       t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
1897       if (t)
1898         return t;
1899       t = walk_tree (&TREE_OPERAND (expr, 1), fold_stmt_r, data, NULL);
1900       if (t)
1901         return t;
1902       *walk_subtrees = 0;
1903
1904       t = maybe_fold_stmt_addition (expr);
1905       break;
1906
1907     case COMPONENT_REF:
1908       t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL);
1909       if (t)
1910         return t;
1911       *walk_subtrees = 0;
1912
1913       /* Make sure the FIELD_DECL is actually a field in the type on
1914          the lhs.  In cases with IMA it is possible that it came
1915          from another, equivalent type at this point.  We have
1916          already checked the equivalence in this case.
1917          Match on type plus offset, to allow for unnamed fields.
1918          We won't necessarily get the corresponding field for
1919          unions; this is believed to be harmless.  */
1920
1921       if ((current_file_decl && TREE_CHAIN (current_file_decl))
1922         && (DECL_FIELD_CONTEXT (TREE_OPERAND (expr, 1)) !=
1923             TREE_TYPE (TREE_OPERAND (expr, 0))))
1924         {
1925           tree f;
1926           tree orig_field = TREE_OPERAND (expr, 1);
1927           tree orig_type = TREE_TYPE (orig_field);
1928           for (f = TYPE_FIELDS (TREE_TYPE (TREE_OPERAND (expr, 0)));
1929               f; f = TREE_CHAIN (f))
1930             {
1931               if (lang_hooks.types_compatible_p (TREE_TYPE (f), orig_type)
1932                   && tree_int_cst_compare (DECL_FIELD_BIT_OFFSET (f),
1933                                           DECL_FIELD_BIT_OFFSET (orig_field))
1934                       == 0
1935                   && tree_int_cst_compare (DECL_FIELD_OFFSET (f),
1936                                           DECL_FIELD_OFFSET (orig_field))
1937                       == 0)
1938                 {
1939                   TREE_OPERAND (expr, 1) = f;
1940                   break;
1941                 }
1942             }
1943         /* Fall through is an error; it will be detected in tree-sra.  */
1944         }
1945       break;
1946
1947     default:
1948       return NULL_TREE;
1949     }
1950
1951   if (t)
1952     {
1953       *expr_p = t;
1954       *changed_p = true;
1955     }
1956
1957   return NULL_TREE;
1958 }
1959
1960 /* Fold the statement pointed by STMT_P.  In some cases, this function may
1961    replace the whole statement with a new one.  Returns true iff folding
1962    makes any changes.  */
1963
1964 bool
1965 fold_stmt (tree *stmt_p)
1966 {
1967   tree rhs, result, stmt;
1968   bool changed = false;
1969
1970   stmt = *stmt_p;
1971
1972   /* If we replaced constants and the statement makes pointer dereferences,
1973      then we may need to fold instances of *&VAR into VAR, etc.  */
1974   if (walk_tree (stmt_p, fold_stmt_r, &changed, NULL))
1975     {
1976       *stmt_p
1977         = build_function_call_expr (implicit_built_in_decls[BUILT_IN_TRAP],
1978                                     NULL);
1979       return true;
1980     }
1981
1982   rhs = get_rhs (stmt);
1983   if (!rhs)
1984     return changed;
1985   result = NULL_TREE;
1986
1987   /* Check for builtins that CCP can handle using information not
1988      available in the generic fold routines.  */
1989   if (TREE_CODE (rhs) == CALL_EXPR)
1990     {
1991       tree callee = get_callee_fndecl (rhs);
1992       if (callee && DECL_BUILT_IN (callee))
1993         result = ccp_fold_builtin (stmt, rhs);
1994     }
1995
1996   /* If we couldn't fold the RHS, hand over to the generic fold routines.  */
1997   if (result == NULL_TREE)
1998     result = fold (rhs);
1999
2000   /* Strip away useless type conversions.  Both the NON_LVALUE_EXPR that
2001      may have been added by fold, and "useless" type conversions that might
2002      now be apparent due to propagation.  */
2003   STRIP_MAIN_TYPE_NOPS (result);
2004   STRIP_USELESS_TYPE_CONVERSION (result);
2005
2006   if (result != rhs)
2007     {
2008       changed = true;
2009       set_rhs (stmt_p, result);
2010     }
2011
2012   return changed;
2013 }
2014
2015 /* Get the main expression from statement STMT.  */
2016
2017 static tree
2018 get_rhs (tree stmt)
2019 {
2020   enum tree_code code = TREE_CODE (stmt);
2021
2022   if (code == MODIFY_EXPR)
2023     return TREE_OPERAND (stmt, 1);
2024   if (code == COND_EXPR)
2025     return COND_EXPR_COND (stmt);
2026   else if (code == SWITCH_EXPR)
2027     return SWITCH_COND (stmt);
2028   else if (code == RETURN_EXPR)
2029     {
2030       if (!TREE_OPERAND (stmt, 0))
2031         return NULL_TREE;
2032       if (TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
2033         return TREE_OPERAND (TREE_OPERAND (stmt, 0), 1);
2034       else
2035         return TREE_OPERAND (stmt, 0);
2036     }
2037   else if (code == GOTO_EXPR)
2038     return GOTO_DESTINATION (stmt);
2039   else if (code == LABEL_EXPR)
2040     return LABEL_EXPR_LABEL (stmt);
2041   else
2042     return stmt;
2043 }
2044
2045
2046 /* Set the main expression of *STMT_P to EXPR.  */
2047
2048 static void
2049 set_rhs (tree *stmt_p, tree expr)
2050 {
2051   tree stmt = *stmt_p;
2052   enum tree_code code = TREE_CODE (stmt);
2053
2054   if (code == MODIFY_EXPR)
2055     TREE_OPERAND (stmt, 1) = expr;
2056   else if (code == COND_EXPR)
2057     COND_EXPR_COND (stmt) = expr;
2058   else if (code == SWITCH_EXPR)
2059     SWITCH_COND (stmt) = expr;
2060   else if (code == RETURN_EXPR)
2061     {
2062       if (TREE_OPERAND (stmt, 0)
2063           && TREE_CODE (TREE_OPERAND (stmt, 0)) == MODIFY_EXPR)
2064         TREE_OPERAND (TREE_OPERAND (stmt, 0), 1) = expr;
2065       else
2066         TREE_OPERAND (stmt, 0) = expr;
2067     }
2068   else if (code == GOTO_EXPR)
2069     GOTO_DESTINATION (stmt) = expr;
2070   else if (code == LABEL_EXPR)
2071     LABEL_EXPR_LABEL (stmt) = expr;
2072   else
2073     {
2074       /* Replace the whole statement with EXPR.  If EXPR has no side
2075          effects, then replace *STMT_P with an empty statement.  */
2076       stmt_ann_t ann = stmt_ann (stmt);
2077       *stmt_p = TREE_SIDE_EFFECTS (expr) ? expr : build_empty_stmt ();
2078       (*stmt_p)->common.ann = (tree_ann) ann;
2079
2080       if (TREE_SIDE_EFFECTS (expr))
2081         {
2082           def_optype defs;
2083           v_may_def_optype v_may_defs;
2084           v_must_def_optype v_must_defs;
2085           size_t i;
2086
2087           /* Fix all the SSA_NAMEs created by *STMT_P to point to its new
2088              replacement.  */
2089           defs = DEF_OPS (ann);
2090           for (i = 0; i < NUM_DEFS (defs); i++)
2091             {
2092               tree var = DEF_OP (defs, i);
2093               if (TREE_CODE (var) == SSA_NAME)
2094                 SSA_NAME_DEF_STMT (var) = *stmt_p;
2095             }
2096
2097           v_may_defs = V_MAY_DEF_OPS (ann);
2098           for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
2099             {
2100               tree var = V_MAY_DEF_RESULT (v_may_defs, i);
2101               if (TREE_CODE (var) == SSA_NAME)
2102                 SSA_NAME_DEF_STMT (var) = *stmt_p;
2103             }
2104
2105           v_must_defs = V_MUST_DEF_OPS (ann);
2106           for (i = 0; i < NUM_V_MUST_DEFS (v_must_defs); i++)
2107             {
2108               tree var = V_MUST_DEF_OP (v_must_defs, i);
2109               if (TREE_CODE (var) == SSA_NAME)
2110                 SSA_NAME_DEF_STMT (var) = *stmt_p;
2111             }
2112         }
2113     }
2114 }
2115
2116
2117 /* Return a default value for variable VAR using the following rules:
2118
2119    1- Global and static variables are considered VARYING, unless they are
2120       declared const.
2121
2122    2- Function arguments are considered VARYING.
2123
2124    3- Any other value is considered UNDEFINED.  This is useful when
2125       considering PHI nodes.  PHI arguments that are undefined do not
2126       change the constant value of the PHI node, which allows for more
2127       constants to be propagated.  */
2128
2129 static value
2130 get_default_value (tree var)
2131 {
2132   value val;
2133   tree sym;
2134
2135   if (TREE_CODE (var) == SSA_NAME)
2136     sym = SSA_NAME_VAR (var);
2137   else
2138     {
2139 #ifdef ENABLE_CHECKING
2140       if (!DECL_P (var))
2141         abort ();
2142 #endif
2143       sym = var;
2144     }
2145
2146   val.lattice_val = UNDEFINED;
2147   val.const_val = NULL_TREE;
2148
2149   if (TREE_CODE (sym) == PARM_DECL || TREE_THIS_VOLATILE (sym))
2150     {
2151       /* Function arguments and volatile variables are considered VARYING.  */
2152       val.lattice_val = VARYING;
2153     }
2154   else if (decl_function_context (sym) != current_function_decl
2155            || TREE_STATIC (sym))
2156     {
2157       /* Globals and static variables are considered VARYING, unless they
2158          are declared 'const'.  */
2159       val.lattice_val = VARYING;
2160
2161       if (TREE_READONLY (sym)
2162           && DECL_INITIAL (sym)
2163           && is_gimple_min_invariant (DECL_INITIAL (sym)))
2164         {
2165           val.lattice_val = CONSTANT;
2166           val.const_val = DECL_INITIAL (sym);
2167         }
2168     }
2169   else
2170     {
2171       enum tree_code code;
2172       tree stmt = SSA_NAME_DEF_STMT (var);
2173
2174       if (!IS_EMPTY_STMT (stmt))
2175         {
2176           code = TREE_CODE (stmt);
2177           if (code != MODIFY_EXPR && code != PHI_NODE)
2178             val.lattice_val = VARYING;
2179         }
2180     }
2181
2182   return val;
2183 }
2184
2185
2186 /* Fold builtin call FN in statement STMT.  If it cannot be folded into a
2187    constant, return NULL_TREE.  Otherwise, return its constant value.  */
2188
2189 static tree
2190 ccp_fold_builtin (tree stmt, tree fn)
2191 {
2192   tree result, strlen_val[2];
2193   tree arglist = TREE_OPERAND (fn, 1), a;
2194   tree callee = get_callee_fndecl (fn);
2195   bitmap visited;
2196   int strlen_arg, i;
2197
2198   /* Ignore MD builtins.  */
2199   if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD)
2200     return NULL_TREE;
2201
2202   /* First try the generic builtin folder.  If that succeeds, return the
2203      result directly.  */
2204   result = fold_builtin (fn);
2205   if (result)
2206     return result;
2207
2208   /* If the builtin could not be folded, and it has no argument list,
2209      we're done.  */
2210   if (!arglist)
2211     return NULL_TREE;
2212
2213   /* Limit the work only for builtins we know how to simplify.  */
2214   switch (DECL_FUNCTION_CODE (callee))
2215     {
2216     case BUILT_IN_STRLEN:
2217     case BUILT_IN_FPUTS:
2218     case BUILT_IN_FPUTS_UNLOCKED:
2219       strlen_arg = 1;
2220       break;
2221     case BUILT_IN_STRCPY:
2222     case BUILT_IN_STRNCPY:
2223       strlen_arg = 2;
2224       break;
2225     default:
2226       return NULL_TREE;
2227     }
2228
2229   /* Try to use the dataflow information gathered by the CCP process.  */
2230   visited = BITMAP_XMALLOC ();
2231
2232   memset (strlen_val, 0, sizeof (strlen_val));
2233   for (i = 0, a = arglist;
2234        strlen_arg;
2235        i++, strlen_arg >>= 1, a = TREE_CHAIN (a))
2236     if (strlen_arg & 1)
2237       {
2238         bitmap_clear (visited);
2239         if (!get_strlen (TREE_VALUE (a), &strlen_val[i], visited))
2240           strlen_val[i] = NULL_TREE;
2241       }
2242
2243   BITMAP_XFREE (visited);
2244
2245   /* FIXME.  All this code looks dangerous in the sense that it might
2246      create non-gimple expressions.  */
2247   switch (DECL_FUNCTION_CODE (callee))
2248     {
2249     case BUILT_IN_STRLEN:
2250       /* Convert from the internal "sizetype" type to "size_t".  */
2251       if (strlen_val[0]
2252           && size_type_node)
2253         {
2254           tree new = convert (size_type_node, strlen_val[0]);
2255
2256           /* If the result is not a valid gimple value, or not a cast
2257              of a valid gimple value, then we can not use the result.  */
2258           if (is_gimple_val (new)
2259               || (is_gimple_cast (new)
2260                   && is_gimple_val (TREE_OPERAND (new, 0))))
2261             return new;
2262           else
2263             return NULL_TREE;
2264         }
2265       return strlen_val[0];
2266     case BUILT_IN_STRCPY:
2267       if (strlen_val[1]
2268           && is_gimple_val (strlen_val[1]))
2269       return simplify_builtin_strcpy (arglist, strlen_val[1]);
2270     case BUILT_IN_STRNCPY:
2271       if (strlen_val[1]
2272           && is_gimple_val (strlen_val[1]))
2273       return simplify_builtin_strncpy (arglist, strlen_val[1]);
2274     case BUILT_IN_FPUTS:
2275       return simplify_builtin_fputs (arglist,
2276                                      TREE_CODE (stmt) != MODIFY_EXPR, 0,
2277                                      strlen_val[0]);
2278     case BUILT_IN_FPUTS_UNLOCKED:
2279       return simplify_builtin_fputs (arglist,
2280                                      TREE_CODE (stmt) != MODIFY_EXPR, 1,
2281                                      strlen_val[0]);
2282
2283     default:
2284       abort ();
2285     }
2286
2287   return NULL_TREE;
2288 }
2289
2290
2291 /* Return the string length of ARG in LENGTH.  If ARG is an SSA name variable,
2292    follow its use-def chains.  If LENGTH is not NULL and its value is not
2293    equal to the length we determine, or if we are unable to determine the
2294    length, return false.  VISITED is a bitmap of visited variables.  */
2295
2296 static bool
2297 get_strlen (tree arg, tree *length, bitmap visited)
2298 {
2299   tree var, def_stmt, val;
2300
2301   if (TREE_CODE (arg) != SSA_NAME)
2302     {
2303       val = c_strlen (arg, 1);
2304       if (!val)
2305         return false;
2306
2307       if (*length && simple_cst_equal (val, *length) != 1)
2308         return false;
2309
2310       *length = val;
2311       return true;
2312     }
2313
2314   /* If we were already here, break the infinite cycle.  */
2315   if (bitmap_bit_p (visited, SSA_NAME_VERSION (arg)))
2316     return true;
2317   bitmap_set_bit (visited, SSA_NAME_VERSION (arg));
2318
2319   var = arg;
2320   def_stmt = SSA_NAME_DEF_STMT (var);
2321
2322   switch (TREE_CODE (def_stmt))
2323     {
2324       case MODIFY_EXPR:
2325         {
2326           tree len, rhs;
2327
2328           /* The RHS of the statement defining VAR must either have a
2329              constant length or come from another SSA_NAME with a constant
2330              length.  */
2331           rhs = TREE_OPERAND (def_stmt, 1);
2332           STRIP_NOPS (rhs);
2333           if (TREE_CODE (rhs) == SSA_NAME)
2334             return get_strlen (rhs, length, visited);
2335
2336           /* See if the RHS is a constant length.  */
2337           len = c_strlen (rhs, 1);
2338           if (len)
2339             {
2340               if (*length && simple_cst_equal (len, *length) != 1)
2341                 return false;
2342
2343               *length = len;
2344               return true;
2345             }
2346
2347           break;
2348         }
2349
2350       case PHI_NODE:
2351         {
2352           /* All the arguments of the PHI node must have the same constant
2353              length.  */
2354           int i;
2355
2356           for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
2357             {
2358               tree arg = PHI_ARG_DEF (def_stmt, i);
2359
2360               /* If this PHI has itself as an argument, we cannot
2361                  determine the string length of this argument.  However,
2362                  if we can find a constant string length for the other
2363                  PHI args then we can still be sure that this is a
2364                  constant string length.  So be optimistic and just
2365                  continue with the next argument.  */
2366               if (arg == PHI_RESULT (def_stmt))
2367                 continue;
2368
2369               if (!get_strlen (arg, length, visited))
2370                 return false;
2371             }
2372
2373           return true;
2374         }
2375
2376       default:
2377         break;
2378     }
2379
2380
2381   return false;
2382 }
2383
2384 \f
2385 /* A simple pass that attempts to fold all builtin functions.  This pass
2386    is run after we've propagated as many constants as we can.  */
2387
2388 static void
2389 execute_fold_all_builtins (void)
2390 {
2391   basic_block bb;
2392   FOR_EACH_BB (bb)
2393     {
2394       block_stmt_iterator i;
2395       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
2396         {
2397           tree *stmtp = bsi_stmt_ptr (i);
2398           tree call = get_rhs (*stmtp);
2399           tree callee, result;
2400
2401           if (!call || TREE_CODE (call) != CALL_EXPR)
2402             continue;
2403           callee = get_callee_fndecl (call);
2404           if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
2405             continue;
2406
2407           result = ccp_fold_builtin (*stmtp, call);
2408           if (!result)
2409             switch (DECL_FUNCTION_CODE (callee))
2410               {
2411               case BUILT_IN_CONSTANT_P:
2412                 /* Resolve __builtin_constant_p.  If it hasn't been
2413                    folded to integer_one_node by now, it's fairly
2414                    certain that the value simply isn't constant.  */
2415                 result = integer_zero_node;
2416                 break;
2417
2418               default:
2419                 continue;
2420               }
2421
2422           if (dump_file && (dump_flags & TDF_DETAILS))
2423             {
2424               fprintf (dump_file, "Simplified\n  ");
2425               print_generic_stmt (dump_file, *stmtp, dump_flags);
2426             }
2427
2428           set_rhs (stmtp, result);
2429           modify_stmt (*stmtp);
2430
2431           if (dump_file && (dump_flags & TDF_DETAILS))
2432             {
2433               fprintf (dump_file, "to\n  ");
2434               print_generic_stmt (dump_file, *stmtp, dump_flags);
2435               fprintf (dump_file, "\n");
2436             }
2437         }
2438     }
2439 }
2440
2441 struct tree_opt_pass pass_fold_builtins =
2442 {
2443   "fab",                                /* name */
2444   NULL,                                 /* gate */
2445   execute_fold_all_builtins,            /* execute */
2446   NULL,                                 /* sub */
2447   NULL,                                 /* next */
2448   0,                                    /* static_pass_number */
2449   0,                                    /* tv_id */
2450   PROP_cfg | PROP_ssa,                  /* properties_required */
2451   0,                                    /* properties_provided */
2452   0,                                    /* properties_destroyed */
2453   0,                                    /* todo_flags_start */
2454   TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
2455 };
2456
2457
2458 #include "gt-tree-ssa-ccp.h"