gcc/tree-ssa-forwprop.c

   1 /* Forward propagation of single use variables.
   2    Copyright (C) 2004, 2005 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "errors.h"
  26 #include "ggc.h"
  27 #include "tree.h"
  28 #include "rtl.h"
  29 #include "tm_p.h"
  30 #include "basic-block.h"
  31 #include "timevar.h"
  32 #include "diagnostic.h"
  33 #include "tree-flow.h"
  34 #include "tree-pass.h"
  35 #include "tree-dump.h"
  36
  37 /* This pass performs simple forward propagation of single use variables
  38    from their definition site into their single use site.
  39
  40    Right now we only bother forward propagating into COND_EXPRs since those
  41    are relatively common cases where forward propagation creates valid
  42    gimple code without the expression needing to fold.  i.e.
  43
  44      bb0:
  45        x = a COND b;
  46        if (x) goto ... else goto ...
  47
  48    Will be transformed into:
  49
  50      bb0:
  51        if (a COND b) goto ... else goto ...
  52
  53    Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
  54
  55    Or (assuming c1 and c2 are constants):
  56
  57      bb0:
  58        x = a + c1;
  59        if (x EQ/NEQ c2) goto ... else goto ...
  60
  61    Will be transformed into:
  62
  63      bb0:
  64         if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
  65
  66    Similarly for x = a - c1.
  67
  68    Or
  69
  70      bb0:
  71        x = !a
  72        if (x) goto ... else goto ...
  73
  74    Will be transformed into:
  75
  76      bb0:
  77         if (a == 0) goto ... else goto ...
  78
  79    Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
  80    For these cases, we propagate A into all, possibly more than one,
  81    COND_EXPRs that use X.
  82
  83    Or
  84
  85      bb0:
  86        x = (typecast) a
  87        if (x) goto ... else goto ...
  88
  89    Will be transformed into:
  90
  91      bb0:
  92         if (a != 0) goto ... else goto ...
  93
  94    (Assuming a is an integral type and x is a boolean or x is an
  95     integral and a is a boolean.)
  96
  97    Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
  98    For these cases, we propagate A into all, possibly more than one,
  99    COND_EXPRs that use X.
 100
 101    In addition to eliminating the variable and the statement which assigns
 102    a value to the variable, we may be able to later thread the jump without
 103    adding insane complexity in the dominator optimizer.
 104
 105    Also note these transformations can cascade.  We handle this by having
 106    a worklist of COND_EXPR statements to examine.  As we make a change to
 107    a statement, we put it back on the worklist to examine on the next
 108    iteration of the main loop.
 109
 110    This will (of course) be extended as other needs arise.  */
 111
 112 /* Bitmap of variables for which we want immediate uses.  This is set
 113    by record_single_argument_cond_exprs and tested in need_imm_uses_for.  */
 114 static bitmap vars;
 115
 116 static bool need_imm_uses_for (tree);
 117 static void tree_ssa_forward_propagate_single_use_vars (void);
 118 static void record_single_argument_cond_exprs (varray_type,
 119                                                varray_type *,
 120                                                bitmap);
 121 static void substitute_single_use_vars (varray_type *, varray_type);
 122
 123 /* Function indicating whether we ought to include information for 'var'
 124    when calculating immediate uses.  */
 125
 126 static bool
 127 need_imm_uses_for (tree var)
 128 {
 129   return bitmap_bit_p (vars, SSA_NAME_VERSION (var));
 130 }
 131
 132 /* Find all COND_EXPRs with a condition that is a naked SSA_NAME or
 133    an equality comparison against a constant.
 134
 135    Record the identified COND_EXPRs and the SSA_NAME used in the COND_EXPR
 136    into a virtual array, which is returned to the caller.  Also record
 137    into VARS that we will need immediate uses for the identified SSA_NAME.
 138
 139    The more uninteresting COND_EXPRs and associated SSA_NAMEs we can
 140    filter out here, the faster this pass will run since its runtime is
 141    dominated by the time to build immediate uses.  */
 142
 143 static void
 144 record_single_argument_cond_exprs (varray_type cond_worklist,
 145                                    varray_type *vars_worklist,
 146                                    bitmap vars)
 147
 148 {
 149   /* The first pass over the blocks gathers the set of variables we need
 150      immediate uses for as well as the set of interesting COND_EXPRs.
 151
 152      A simpler implementation may be appropriate if/when we have a lower
 153      overhead means of getting immediate use information.  */
 154   while (VARRAY_ACTIVE_SIZE (cond_worklist) > 0)
 155     {
 156       tree last = VARRAY_TOP_TREE (cond_worklist);
 157
 158       VARRAY_POP (cond_worklist);
 159
 160       /* See if this block ends in a COND_EXPR.  */
 161       if (last && TREE_CODE (last) == COND_EXPR)
 162         {
 163           tree cond = COND_EXPR_COND (last);
 164           enum tree_code cond_code = TREE_CODE (cond);
 165
 166           /* If the condition is a lone variable or an equality test of
 167              an SSA_NAME against an integral constant, then we may have an
 168              optimizable case.
 169
 170              Note these conditions also ensure the COND_EXPR has no
 171              virtual operands or other side effects.  */
 172           if (cond_code == SSA_NAME
 173               || ((cond_code == EQ_EXPR || cond_code == NE_EXPR)
 174                   && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
 175                   && CONSTANT_CLASS_P (TREE_OPERAND (cond, 1))
 176                   && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
 177             {
 178               tree def;
 179               tree test_var;
 180
 181               /* Extract the single variable used in the test into TEST_VAR.  */
 182               if (cond_code == SSA_NAME)
 183                 test_var = cond;
 184               else
 185                 test_var = TREE_OPERAND (cond, 0);
 186
 187               /* If we have already recorded this SSA_NAME as interesting,
 188                  do not do so again.  */
 189               if (bitmap_bit_p (vars, SSA_NAME_VERSION (test_var)))
 190                 continue;
 191
 192               /* Now get the defining statement for TEST_VAR and see if it
 193                  something we are interested in.  */
 194               def = SSA_NAME_DEF_STMT (test_var);
 195               if (TREE_CODE (def) == MODIFY_EXPR)
 196                 {
 197                   tree def_rhs = TREE_OPERAND (def, 1);
 198
 199                   /* If TEST_VAR is set by adding or subtracting a constant
 200                      from an SSA_NAME, then it is interesting to us as we
 201                      can adjust the constant in the conditional and thus
 202                      eliminate the arithmetic operation.  */
 203                   if (TREE_CODE (def_rhs) == PLUS_EXPR
 204                          || TREE_CODE (def_rhs) == MINUS_EXPR)
 205                     {
 206                       tree op0 = TREE_OPERAND (def_rhs, 0);
 207                       tree op1 = TREE_OPERAND (def_rhs, 1);
 208
 209                       /* The first operand must be an SSA_NAME and the second
 210                          operand must be a constant.  */
 211                       if (TREE_CODE (op0) != SSA_NAME
 212                           || !CONSTANT_CLASS_P (op1)
 213                           || !INTEGRAL_TYPE_P (TREE_TYPE (op1)))
 214                         continue;
 215
 216                       /* Don't propagate if the first operand occurs in
 217                          an abnormal PHI.  */
 218                       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
 219                         continue;
 220                     }
 221
 222                   /* These cases require comparisons of a naked SSA_NAME or
 223                      comparison of an SSA_NAME against zero or one.  */
 224                   else if (TREE_CODE (cond) == SSA_NAME
 225                            || integer_zerop (TREE_OPERAND (cond, 1))
 226                            || integer_onep (TREE_OPERAND (cond, 1)))
 227                     {
 228                       /* If TEST_VAR is set from a relational operation
 229                          between two SSA_NAMEs or a combination of an SSA_NAME
 230                          and a constant, then it is interesting.  */
 231                       if (COMPARISON_CLASS_P (def_rhs))
 232                         {
 233                           tree op0 = TREE_OPERAND (def_rhs, 0);
 234                           tree op1 = TREE_OPERAND (def_rhs, 1);
 235
 236                           /* Both operands of DEF_RHS must be SSA_NAMEs or
 237                              constants.  */
 238                           if ((TREE_CODE (op0) != SSA_NAME
 239                                && !is_gimple_min_invariant (op0))
 240                               || (TREE_CODE (op1) != SSA_NAME
 241                                   && !is_gimple_min_invariant (op1)))
 242                             continue;
 243
 244                           /* Don't propagate if the first operand occurs in
 245                              an abnormal PHI.  */
 246                           if (TREE_CODE (op0) == SSA_NAME
 247                               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
 248                             continue;
 249
 250                           /* Don't propagate if the second operand occurs in
 251                              an abnormal PHI.  */
 252                           if (TREE_CODE (op1) == SSA_NAME
 253                               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))
 254                             continue;
 255                         }
 256
 257                       /* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it
 258                          is interesting.  */
 259                       else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR)
 260                         {
 261                           def_rhs = TREE_OPERAND (def_rhs, 0);
 262
 263                           /* DEF_RHS must be an SSA_NAME or constant.  */
 264                           if (TREE_CODE (def_rhs) != SSA_NAME
 265                               && !is_gimple_min_invariant (def_rhs))
 266                             continue;
 267
 268                           /* Don't propagate if the operand occurs in
 269                              an abnormal PHI.  */
 270                           if (TREE_CODE (def_rhs) == SSA_NAME
 271                               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_rhs))
 272                             continue;
 273                         }
 274
 275                       /* If TEST_VAR was set from a cast of an integer type
 276                          to a boolean type or a cast of a boolean to an
 277                          integral, then it is interesting.  */
 278                       else if (TREE_CODE (def_rhs) == NOP_EXPR
 279                                || TREE_CODE (def_rhs) == CONVERT_EXPR)
 280                         {
 281                           tree outer_type;
 282                           tree inner_type;
 283
 284                           outer_type = TREE_TYPE (def_rhs);
 285                           inner_type = TREE_TYPE (TREE_OPERAND (def_rhs, 0));
 286
 287                           if ((TREE_CODE (outer_type) == BOOLEAN_TYPE
 288                                && INTEGRAL_TYPE_P (inner_type))
 289                               || (TREE_CODE (inner_type) == BOOLEAN_TYPE
 290                                   && INTEGRAL_TYPE_P (outer_type)))
 291                             ;
 292                           else
 293                             continue;
 294
 295                           /* Don't propagate if the operand occurs in
 296                              an abnormal PHI.  */
 297                           if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
 298                               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND
 299                                                                   (def_rhs, 0)))
 300                             continue;
 301                         }
 302                       else
 303                         continue;
 304                     }
 305                   else
 306                     continue;
 307
 308                   /* All the tests passed, record TEST_VAR as interesting.  */
 309                   VARRAY_PUSH_TREE (*vars_worklist, test_var);
 310                   bitmap_set_bit (vars, SSA_NAME_VERSION (test_var));
 311                 }
 312             }
 313         }
 314     }
 315 }
 316
 317 /* Given FORWPROP_DATA containing SSA_NAMEs which are used in COND_EXPRs
 318    that we may be able to optimize, attempt to rewrite the condition
 319    in each COND_EXPR to use the RHS of the statement which defines the
 320    SSA_NAME used in the COND_EXPR.  */
 321
 322 static void
 323 substitute_single_use_vars (varray_type *cond_worklist,
 324                             varray_type vars_worklist)
 325 {
 326   while (VARRAY_ACTIVE_SIZE (vars_worklist) > 0)
 327     {
 328       tree test_var = VARRAY_TOP_TREE (vars_worklist);
 329       tree def = SSA_NAME_DEF_STMT (test_var);
 330       dataflow_t df;
 331       int j, num_uses, propagated_uses;
 332
 333       VARRAY_POP (vars_worklist);
 334
 335       /* Now compute the immediate uses of TEST_VAR.  */
 336       df = get_immediate_uses (def);
 337       num_uses = num_immediate_uses (df);
 338       propagated_uses = 0;
 339
 340       /* If TEST_VAR is used more than once and is not a boolean set
 341          via TRUTH_NOT_EXPR with another SSA_NAME as its argument, then
 342          we can not optimize.  */
 343       if (num_uses == 1
 344           || (TREE_CODE (TREE_TYPE (test_var)) == BOOLEAN_TYPE
 345               && TREE_CODE (TREE_OPERAND (def, 1)) == TRUTH_NOT_EXPR
 346               && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (def, 1), 0))
 347                   == SSA_NAME)))
 348         ;
 349       else
 350         continue;
 351
 352       /* Walk over each use and try to forward propagate the RHS of
 353          DEF into the use.  */
 354       for (j = 0; j < num_uses; j++)
 355         {
 356           tree cond_stmt;
 357           tree cond;
 358           enum tree_code cond_code;
 359           tree def_rhs;
 360           enum tree_code def_rhs_code;
 361           tree new_cond;
 362
 363           cond_stmt = immediate_use (df, j);
 364
 365           /* For now we can only propagate into COND_EXPRs.  */
 366           if (TREE_CODE (cond_stmt) != COND_EXPR)
 367             continue;
 368
 369           cond = COND_EXPR_COND (cond_stmt);
 370           cond_code = TREE_CODE (cond);
 371           def_rhs = TREE_OPERAND (def, 1);
 372           def_rhs_code = TREE_CODE (def_rhs);
 373
 374           /* If the definition of the single use variable was from an
 375              arithmetic operation, then we just need to adjust the
 376              constant in the COND_EXPR_COND and update the variable tested.  */
 377           if (def_rhs_code == PLUS_EXPR || def_rhs_code == MINUS_EXPR)
 378             {
 379               tree op0 = TREE_OPERAND (def_rhs, 0);
 380               tree op1 = TREE_OPERAND (def_rhs, 1);
 381               enum tree_code new_code;
 382               tree t;
 383
 384               /* If the variable was defined via X + C, then we must subtract
 385                  C from the constant in the conditional.  Otherwise we add
 386                  C to the constant in the conditional.  The result must fold
 387                  into a valid gimple operand to be optimizable.  */
 388               new_code = def_rhs_code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR;
 389               t = int_const_binop (new_code, TREE_OPERAND (cond, 1), op1, 0);
 390               if (!is_gimple_val (t))
 391                 continue;
 392
 393               new_cond = build (cond_code, boolean_type_node, op0, t);
 394             }
 395           /* If the variable is defined by a conditional expression... */
 396           else if (TREE_CODE_CLASS (def_rhs_code) == tcc_comparison)
 397             {
 398               /* TEST_VAR was set from a relational operator.  */
 399               tree op0 = TREE_OPERAND (def_rhs, 0);
 400               tree op1 = TREE_OPERAND (def_rhs, 1);
 401
 402               new_cond = build (def_rhs_code, boolean_type_node, op0, op1);
 403
 404               /* Invert the conditional if necessary.  */
 405               if ((cond_code == EQ_EXPR
 406                    && integer_zerop (TREE_OPERAND (cond, 1)))
 407                   || (cond_code == NE_EXPR
 408                       && integer_onep (TREE_OPERAND (cond, 1))))
 409                 {
 410                   new_cond = invert_truthvalue (new_cond);
 411
 412                   /* If we did not get a simple relational expression or
 413                      bare SSA_NAME, then we can not optimize this case.  */
 414                   if (!COMPARISON_CLASS_P (new_cond)
 415                       && TREE_CODE (new_cond) != SSA_NAME)
 416                     continue;
 417                 }
 418             }
 419           else
 420             {
 421               bool invert = false;
 422               enum tree_code new_code;
 423               tree new_arg;
 424
 425               /* TEST_VAR was set from a TRUTH_NOT_EXPR or a NOP_EXPR.  */
 426               if (def_rhs_code == TRUTH_NOT_EXPR)
 427                 invert = true;
 428
 429               if (cond_code == SSA_NAME
 430                   || (cond_code == NE_EXPR
 431                       && integer_zerop (TREE_OPERAND (cond, 1)))
 432                   || (cond_code == EQ_EXPR
 433                       && integer_onep (TREE_OPERAND (cond, 1))))
 434                 new_code = NE_EXPR;
 435               else
 436                 new_code = EQ_EXPR;
 437
 438               if (invert)
 439                 new_code = (new_code == EQ_EXPR ? NE_EXPR  : EQ_EXPR);
 440
 441               new_arg = TREE_OPERAND (def_rhs, 0);
 442               new_cond = build2 (new_code, boolean_type_node, new_arg,
 443                                  fold_convert (TREE_TYPE (new_arg),
 444                                                integer_zero_node));
 445             }
 446
 447           /* Dump details.  */
 448           if (dump_file && (dump_flags & TDF_DETAILS))
 449             {
 450               fprintf (dump_file, "  Replaced '");
 451               print_generic_expr (dump_file, cond, dump_flags);
 452               fprintf (dump_file, "' with '");
 453               print_generic_expr (dump_file, new_cond, dump_flags);
 454               fprintf (dump_file, "'\n");
 455             }
 456
 457           /* Replace the condition.  */
 458           COND_EXPR_COND (cond_stmt) = new_cond;
 459           modify_stmt (cond_stmt);
 460           propagated_uses++;
 461           VARRAY_PUSH_TREE (*cond_worklist, cond_stmt);
 462         }
 463
 464       /* If we propagated into all the uses, then we can delete DEF.
 465          Unfortunately, we have to find the defining statement in
 466          whatever block it might be in.  */
 467       if (num_uses && num_uses == propagated_uses)
 468         {
 469           block_stmt_iterator bsi = bsi_for_stmt (def);
 470           bsi_remove (&bsi);
 471         }
 472     }
 473 }
 474
 475 /* Main entry point for the forward propagation optimizer.  */
 476
 477 static void
 478 tree_ssa_forward_propagate_single_use_vars (void)
 479 {
 480   basic_block bb;
 481   varray_type vars_worklist, cond_worklist;
 482
 483   vars = BITMAP_ALLOC (NULL);
 484   VARRAY_TREE_INIT (vars_worklist, 10, "VARS worklist");
 485   VARRAY_TREE_INIT (cond_worklist, 10, "COND worklist");
 486
 487   /* Prime the COND_EXPR worklist by placing all the COND_EXPRs on the
 488      worklist.  */
 489   FOR_EACH_BB (bb)
 490     {
 491       tree last = last_stmt (bb);
 492       if (last && TREE_CODE (last) == COND_EXPR)
 493         VARRAY_PUSH_TREE (cond_worklist, last);
 494     }
 495
 496   while (VARRAY_ACTIVE_SIZE (cond_worklist) > 0)
 497     {
 498       /* First get a list of all the interesting COND_EXPRs and potential
 499          single use variables which feed those COND_EXPRs.  This will drain
 500          COND_WORKLIST and initialize VARS_WORKLIST.  */
 501       record_single_argument_cond_exprs (cond_worklist, &vars_worklist, vars);
 502
 503       if (VARRAY_ACTIVE_SIZE (vars_worklist) > 0)
 504         {
 505           /* Now compute immediate uses for all the variables we care about.  */
 506           compute_immediate_uses (TDFA_USE_OPS, need_imm_uses_for);
 507
 508           /* We've computed immediate uses, so we can/must clear the VARS
 509              bitmap for the next iteration.  */
 510           bitmap_clear (vars);
 511
 512           /* And optimize.  This will drain VARS_WORKLIST and initialize
 513              COND_WORKLIST for the next iteration.  */
 514           substitute_single_use_vars (&cond_worklist, vars_worklist);
 515
 516           /* We do not incrementally update the dataflow information
 517              so we must free it here and recompute the necessary bits
 518              on the next iteration.  If this turns out to be expensive,
 519              methods for incrementally updating the dataflow are known.  */
 520           free_df ();
 521         }
 522     }
 523
 524   /* All done.  Clean up.  */
 525   BITMAP_FREE (vars);
 526 }
 527
 528
 529 static bool
 530 gate_forwprop (void)
 531 {
 532   return 1;
 533 }
 534
 535 struct tree_opt_pass pass_forwprop = {
 536   "forwprop",                   /* name */
 537   gate_forwprop,                /* gate */
 538   tree_ssa_forward_propagate_single_use_vars,   /* execute */
 539   NULL,                         /* sub */
 540   NULL,                         /* next */
 541   0,                            /* static_pass_number */
 542   TV_TREE_FORWPROP,             /* tv_id */
 543   PROP_cfg | PROP_ssa
 544     | PROP_alias,               /* properties_required */
 545   0,                            /* properties_provided */
 546   0,                            /* properties_destroyed */
 547   0,                            /* todo_flags_start */
 548   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 549   | TODO_verify_ssa,
 550   0                                     /* letter */
 551 };