gcc/tree-ssa-forwprop.c

   1 /* Forward propagation of single use variables.
   2    Copyright (C) 2004 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       block_stmt_iterator bsi;
 333
 334       VARRAY_POP (vars_worklist);
 335
 336       /* Now compute the immediate uses of TEST_VAR.  */
 337       df = get_immediate_uses (def);
 338       num_uses = num_immediate_uses (df);
 339       propagated_uses = 0;
 340
 341       /* If TEST_VAR is used more than once and is not a boolean set
 342          via TRUTH_NOT_EXPR with another SSA_NAME as its argument, then
 343          we can not optimize.  */
 344       if (num_uses == 1
 345           || (TREE_CODE (TREE_TYPE (test_var)) == BOOLEAN_TYPE
 346               && TREE_CODE (TREE_OPERAND (def, 1)) == TRUTH_NOT_EXPR
 347               && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (def, 1), 0))
 348                   == SSA_NAME)))
 349         ;
 350       else
 351         continue;
 352
 353       /* Walk over each use and try to forward propagate the RHS of
 354          DEF into the use.  */
 355       for (j = 0; j < num_uses; j++)
 356         {
 357           tree cond_stmt;
 358           tree cond;
 359           enum tree_code cond_code;
 360           tree def_rhs;
 361           enum tree_code def_rhs_code;
 362           tree new_cond;
 363
 364           cond_stmt = immediate_use (df, j);
 365
 366           /* For now we can only propagate into COND_EXPRs.  */
 367           if (TREE_CODE (cond_stmt) != COND_EXPR)
 368             continue;
 369
 370           cond = COND_EXPR_COND (cond_stmt);
 371           cond_code = TREE_CODE (cond);
 372           def_rhs = TREE_OPERAND (def, 1);
 373           def_rhs_code = TREE_CODE (def_rhs);
 374
 375           /* If the definition of the single use variable was from an
 376              arithmetic operation, then we just need to adjust the
 377              constant in the COND_EXPR_COND and update the variable tested.  */
 378           if (def_rhs_code == PLUS_EXPR || def_rhs_code == MINUS_EXPR)
 379             {
 380               tree op0 = TREE_OPERAND (def_rhs, 0);
 381               tree op1 = TREE_OPERAND (def_rhs, 1);
 382               enum tree_code new_code;
 383               tree t;
 384
 385               /* If the variable was defined via X + C, then we must subtract
 386                  C from the constant in the conditional.  Otherwise we add
 387                  C to the constant in the conditional.  The result must fold
 388                  into a valid gimple operand to be optimizable.  */
 389               new_code = def_rhs_code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR;
 390               t = int_const_binop (new_code, TREE_OPERAND (cond, 1), op1, 0);
 391               if (!is_gimple_val (t))
 392                 continue;
 393
 394               new_cond = build (cond_code, boolean_type_node, op0, t);
 395             }
 396           /* If the variable is defined by a conditional expression... */
 397           else if (TREE_CODE_CLASS (def_rhs_code) == tcc_comparison)
 398             {
 399               /* TEST_VAR was set from a relational operator.  */
 400               tree op0 = TREE_OPERAND (def_rhs, 0);
 401               tree op1 = TREE_OPERAND (def_rhs, 1);
 402
 403               new_cond = build (def_rhs_code, boolean_type_node, op0, op1);
 404
 405               /* Invert the conditional if necessary.  */
 406               if ((cond_code == EQ_EXPR
 407                    && integer_zerop (TREE_OPERAND (cond, 1)))
 408                   || (cond_code == NE_EXPR
 409                       && integer_onep (TREE_OPERAND (cond, 1))))
 410                 {
 411                   new_cond = invert_truthvalue (new_cond);
 412
 413                   /* If we did not get a simple relational expression or
 414                      bare SSA_NAME, then we can not optimize this case.  */
 415                   if (!COMPARISON_CLASS_P (new_cond)
 416                       && TREE_CODE (new_cond) != SSA_NAME)
 417                     continue;
 418                 }
 419             }
 420           else
 421             {
 422               bool invert = false;
 423               enum tree_code new_code;
 424               tree new_arg;
 425
 426               /* TEST_VAR was set from a TRUTH_NOT_EXPR or a NOP_EXPR.  */
 427               if (def_rhs_code == TRUTH_NOT_EXPR)
 428                 invert = true;
 429
 430               if (cond_code == SSA_NAME
 431                   || (cond_code == NE_EXPR
 432                       && integer_zerop (TREE_OPERAND (cond, 1)))
 433                   || (cond_code == EQ_EXPR
 434                       && integer_onep (TREE_OPERAND (cond, 1))))
 435                 new_code = NE_EXPR;
 436               else
 437                 new_code = EQ_EXPR;
 438
 439               if (invert)
 440                 new_code = (new_code == EQ_EXPR ? NE_EXPR  : EQ_EXPR);
 441
 442               new_arg = TREE_OPERAND (def_rhs, 0);
 443               new_cond = build2 (new_code, boolean_type_node, new_arg,
 444                                  fold_convert (TREE_TYPE (new_arg),
 445                                                integer_zero_node));
 446             }
 447
 448           /* Dump details.  */
 449           if (dump_file && (dump_flags & TDF_DETAILS))
 450             {
 451               fprintf (dump_file, "  Replaced '");
 452               print_generic_expr (dump_file, cond, dump_flags);
 453               fprintf (dump_file, "' with '");
 454               print_generic_expr (dump_file, new_cond, dump_flags);
 455               fprintf (dump_file, "'\n");
 456             }
 457
 458           /* Replace the condition.  */
 459           COND_EXPR_COND (cond_stmt) = new_cond;
 460           modify_stmt (cond_stmt);
 461           propagated_uses++;
 462           VARRAY_PUSH_TREE (*cond_worklist, cond_stmt);
 463         }
 464
 465       /* If we propagated into all the uses, then we can delete DEF.
 466          Unfortunately, we have to find the defining statement in
 467          whatever block it might be in.  */
 468       if (num_uses && num_uses == propagated_uses)
 469         for (bsi = bsi_start (bb_for_stmt (def));
 470              !bsi_end_p (bsi);
 471              bsi_next (&bsi))
 472           {
 473             if (def == bsi_stmt (bsi))
 474               {
 475                 bsi_remove (&bsi);
 476                 break;
 477               }
 478           }
 479     }
 480 }
 481
 482 /* Main entry point for the forward propagation optimizer.  */
 483
 484 static void
 485 tree_ssa_forward_propagate_single_use_vars (void)
 486 {
 487   basic_block bb;
 488   varray_type vars_worklist, cond_worklist;
 489
 490   vars = BITMAP_XMALLOC ();
 491   VARRAY_TREE_INIT (vars_worklist, 10, "VARS worklist");
 492   VARRAY_TREE_INIT (cond_worklist, 10, "COND worklist");
 493
 494   /* Prime the COND_EXPR worklist by placing all the COND_EXPRs on the
 495      worklist.  */
 496   FOR_EACH_BB (bb)
 497     {
 498       tree last = last_stmt (bb);
 499       if (last && TREE_CODE (last) == COND_EXPR)
 500         VARRAY_PUSH_TREE (cond_worklist, last);
 501     }
 502
 503   while (VARRAY_ACTIVE_SIZE (cond_worklist) > 0)
 504     {
 505       /* First get a list of all the interesting COND_EXPRs and potential
 506          single use variables which feed those COND_EXPRs.  This will drain
 507          COND_WORKLIST and initialize VARS_WORKLIST.  */
 508       record_single_argument_cond_exprs (cond_worklist, &vars_worklist, vars);
 509
 510       if (VARRAY_ACTIVE_SIZE (vars_worklist) > 0)
 511         {
 512           /* Now compute immediate uses for all the variables we care about.  */
 513           compute_immediate_uses (TDFA_USE_OPS, need_imm_uses_for);
 514
 515           /* We've computed immediate uses, so we can/must clear the VARS
 516              bitmap for the next iteration.  */
 517           bitmap_clear (vars);
 518
 519           /* And optimize.  This will drain VARS_WORKLIST and initialize
 520              COND_WORKLIST for the next iteration.  */
 521           substitute_single_use_vars (&cond_worklist, vars_worklist);
 522
 523           /* We do not incrementally update the dataflow information
 524              so we must free it here and recompute the necessary bits
 525              on the next iteration.  If this turns out to be expensive,
 526              methods for incrementally updating the dataflow are known.  */
 527           free_df ();
 528         }
 529     }
 530
 531   /* All done.  Clean up.  */
 532   BITMAP_XFREE (vars);
 533 }
 534
 535
 536 static bool
 537 gate_forwprop (void)
 538 {
 539   return 1;
 540 }
 541
 542 struct tree_opt_pass pass_forwprop = {
 543   "forwprop",                   /* name */
 544   gate_forwprop,                /* gate */
 545   tree_ssa_forward_propagate_single_use_vars,   /* execute */
 546   NULL,                         /* sub */
 547   NULL,                         /* next */
 548   0,                            /* static_pass_number */
 549   TV_TREE_FORWPROP,             /* tv_id */
 550   PROP_cfg | PROP_ssa
 551     | PROP_alias,               /* properties_required */
 552   0,                            /* properties_provided */
 553   0,                            /* properties_destroyed */
 554   0,                            /* todo_flags_start */
 555   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 556   | TODO_verify_ssa,
 557   0                                     /* letter */
 558 };