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.  ie
  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                   && TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (cond, 1))) == 'c'
 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                           || TREE_CODE_CLASS (TREE_CODE (op1)) != 'c'
 213                           || !INTEGRAL_TYPE_P (TREE_TYPE (op1)))
 214                         continue;
 215                     }
 216
 217                   /* These cases require comparisons of a naked SSA_NAME or
 218                      comparison of an SSA_NAME against zero or one.  */
 219                   else if (TREE_CODE (cond) == SSA_NAME
 220                            || integer_zerop (TREE_OPERAND (cond, 1))
 221                            || integer_onep (TREE_OPERAND (cond, 1)))
 222                     {
 223                       /* If TEST_VAR is set from a relational operation
 224                          between two SSA_NAMEs or a combination of an SSA_NAME
 225                          and a constant, then it is interesting.  */
 226                       if (TREE_CODE_CLASS (TREE_CODE (def_rhs)) == '<')
 227                         {
 228                           tree op0 = TREE_OPERAND (def_rhs, 0);
 229                           tree op1 = TREE_OPERAND (def_rhs, 1);
 230
 231                           /* Both operands of DEF_RHS must be SSA_NAMEs or
 232                              constants.  */
 233                           if ((TREE_CODE (op0) != SSA_NAME
 234                                && !is_gimple_min_invariant (op0))
 235                               || (TREE_CODE (op1) != SSA_NAME
 236                                   && !is_gimple_min_invariant (op1)))
 237                             continue;
 238                         }
 239
 240                       /* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it
 241                          is interesting.  */
 242                       else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR)
 243                         {
 244                           def_rhs = TREE_OPERAND (def_rhs, 0);
 245
 246                           /* DEF_RHS must be an SSA_NAME or constant.  */
 247                           if (TREE_CODE (def_rhs) != SSA_NAME
 248                               && !is_gimple_min_invariant (def_rhs))
 249                             continue;
 250                         }
 251
 252                       /* If TEST_VAR was set from a cast of an integer type
 253                          to a boolean type or a cast of a boolean to an
 254                          integral, then it is interesting.  */
 255                       else if (TREE_CODE (def_rhs) == NOP_EXPR
 256                                || TREE_CODE (def_rhs) == CONVERT_EXPR)
 257                         {
 258                           tree outer_type;
 259                           tree inner_type;
 260
 261                           outer_type = TREE_TYPE (def_rhs);
 262                           inner_type = TREE_TYPE (TREE_OPERAND (def_rhs, 0));
 263
 264                           if ((TREE_CODE (outer_type) == BOOLEAN_TYPE
 265                                && INTEGRAL_TYPE_P (inner_type))
 266                               || (TREE_CODE (inner_type) == BOOLEAN_TYPE
 267                                   && INTEGRAL_TYPE_P (outer_type)))
 268                             ;
 269                           else
 270                             continue;
 271                         }
 272                       else
 273                         continue;
 274                     }
 275                   else
 276                     continue;
 277
 278                   /* All the tests passed, record TEST_VAR as interesting.  */
 279                   VARRAY_PUSH_TREE (*vars_worklist, test_var);
 280                   bitmap_set_bit (vars, SSA_NAME_VERSION (test_var));
 281                 }
 282             }
 283         }
 284     }
 285 }
 286
 287 /* Given FORWPROP_DATA containing SSA_NAMEs which are used in COND_EXPRs
 288    that we may be able to optimize, attempt to rewrite the condition
 289    in each COND_EXPR to use the RHS of the statement which defines the
 290    SSA_NAME used in the COND_EXPR.  */
 291
 292 static void
 293 substitute_single_use_vars (varray_type *cond_worklist,
 294                             varray_type vars_worklist)
 295 {
 296   while (VARRAY_ACTIVE_SIZE (vars_worklist) > 0)
 297     {
 298       tree test_var = VARRAY_TOP_TREE (vars_worklist);
 299       tree def = SSA_NAME_DEF_STMT (test_var);
 300       dataflow_t df;
 301       int j, num_uses, propagated_uses;
 302       block_stmt_iterator bsi;
 303
 304       VARRAY_POP (vars_worklist);
 305
 306       /* Now compute the immediate uses of TEST_VAR.  */
 307       df = get_immediate_uses (def);
 308       num_uses = num_immediate_uses (df);
 309       propagated_uses = 0;
 310
 311       /* If TEST_VAR is used more than once and is not a boolean set
 312          via TRUTH_NOT_EXPR with another SSA_NAME as its argument, then
 313          we can not optimize.  */
 314       if (num_uses == 1
 315           || (TREE_CODE (TREE_TYPE (test_var)) == BOOLEAN_TYPE
 316               && TREE_CODE (TREE_OPERAND (def, 1)) == TRUTH_NOT_EXPR
 317               && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (def, 1), 0))
 318                   == SSA_NAME)))
 319         ;
 320       else
 321         continue;
 322
 323       /* Walk over each use and try to forward propagate the RHS of
 324          DEF into the use.  */
 325       for (j = 0; j < num_uses; j++)
 326         {
 327           tree cond_stmt;
 328           tree cond;
 329           enum tree_code cond_code;
 330           tree def_rhs;
 331           enum tree_code def_rhs_code;
 332           tree new_cond;
 333
 334           cond_stmt = immediate_use (df, j);
 335
 336           /* For now we can only propagate into COND_EXPRs.  */
 337           if (TREE_CODE (cond_stmt) != COND_EXPR)
 338             continue;
 339
 340           cond = COND_EXPR_COND (cond_stmt);
 341           cond_code = TREE_CODE (cond);
 342           def_rhs = TREE_OPERAND (def, 1);
 343           def_rhs_code = TREE_CODE (def_rhs);
 344
 345           /* If the definition of the single use variable was from an
 346              arithmetic operation, then we just need to adjust the
 347              constant in the COND_EXPR_COND and update the variable tested.  */
 348           if (def_rhs_code == PLUS_EXPR || def_rhs_code == MINUS_EXPR)
 349             {
 350               tree op0 = TREE_OPERAND (def_rhs, 0);
 351               tree op1 = TREE_OPERAND (def_rhs, 1);
 352               enum tree_code new_code;
 353               tree t;
 354
 355               /* If the variable was defined via X + C, then we must subtract
 356                  C from the constant in the conditional.  Otherwise we add
 357                  C to the constant in the conditional.  The result must fold
 358                  into a valid gimple operand to be optimizable.  */
 359               new_code = def_rhs_code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR;
 360               t = int_const_binop (new_code, TREE_OPERAND (cond, 1), op1, 0);
 361               if (!is_gimple_val (t))
 362                 continue;
 363
 364               new_cond = build (cond_code, boolean_type_node, op0, t);
 365             }
 366           /* If the variable is defined by a conditional expression... */
 367           else if (TREE_CODE_CLASS (def_rhs_code) == '<')
 368             {
 369               /* TEST_VAR was set from a relational operator.  */
 370               tree op0 = TREE_OPERAND (def_rhs, 0);
 371               tree op1 = TREE_OPERAND (def_rhs, 1);
 372
 373               new_cond = build (def_rhs_code, boolean_type_node, op0, op1);
 374
 375               /* Invert the conditional if necessary.  */
 376               if ((cond_code == EQ_EXPR
 377                    && integer_zerop (TREE_OPERAND (cond, 1)))
 378                   || (cond_code == NE_EXPR
 379                       && integer_onep (TREE_OPERAND (cond, 1))))
 380                 {
 381                   new_cond = invert_truthvalue (new_cond);
 382
 383                   /* If we did not get a simple relational expression or
 384                      bare SSA_NAME, then we can not optimize this case.  */
 385                   if (TREE_CODE_CLASS (TREE_CODE (new_cond)) != '<'
 386                       && TREE_CODE (new_cond) != SSA_NAME)
 387                     continue;
 388                 }
 389             }
 390           else
 391             {
 392               bool invert = false;
 393               enum tree_code new_code;
 394
 395               /* TEST_VAR was set from a TRUTH_NOT_EXPR or a NOP_EXPR.  */
 396               if (def_rhs_code == TRUTH_NOT_EXPR)
 397                 invert = true;
 398
 399               if (cond_code == SSA_NAME
 400                   || (cond_code == NE_EXPR
 401                       && integer_zerop (TREE_OPERAND (cond, 1)))
 402                   || (cond_code == EQ_EXPR
 403                       && integer_onep (TREE_OPERAND (cond, 1))))
 404                 new_code = NE_EXPR;
 405               else
 406                 new_code = EQ_EXPR;
 407
 408               if (invert)
 409                 new_code = (new_code == EQ_EXPR ? NE_EXPR  : EQ_EXPR);
 410
 411               new_cond = build (new_code,
 412                                 boolean_type_node,
 413                                 TREE_OPERAND (def_rhs, 0),
 414                                 convert (TREE_TYPE (def_rhs),
 415                                          integer_zero_node));
 416             }
 417
 418           /* Dump details.  */
 419           if (dump_file && (dump_flags & TDF_DETAILS))
 420             {
 421               fprintf (dump_file, "  Replaced '");
 422               print_generic_expr (dump_file, cond, dump_flags);
 423               fprintf (dump_file, "' with '");
 424               print_generic_expr (dump_file, new_cond, dump_flags);
 425               fprintf (dump_file, "'\n");
 426             }
 427
 428           /* Replace the condition.  */
 429           COND_EXPR_COND (cond_stmt) = new_cond;
 430           modify_stmt (cond_stmt);
 431           propagated_uses++;
 432           VARRAY_PUSH_TREE (*cond_worklist, cond_stmt);
 433         }
 434
 435       /* If we propagated into all the uses, then we can delete DEF.
 436          Unfortunately, we have to find the defining statement in
 437          whatever block it might be in.  */
 438       if (num_uses && num_uses == propagated_uses)
 439         for (bsi = bsi_start (bb_for_stmt (def));
 440              !bsi_end_p (bsi);
 441              bsi_next (&bsi))
 442           {
 443             if (def == bsi_stmt (bsi))
 444               {
 445                 bsi_remove (&bsi);
 446                 break;
 447               }
 448           }
 449     }
 450 }
 451
 452 /* Main entry point for the forward propagation optimizer.  */
 453
 454 static void
 455 tree_ssa_forward_propagate_single_use_vars (void)
 456 {
 457   basic_block bb;
 458   varray_type vars_worklist, cond_worklist;
 459
 460   vars = BITMAP_XMALLOC ();
 461   VARRAY_TREE_INIT (vars_worklist, 10, "VARS worklist");
 462   VARRAY_TREE_INIT (cond_worklist, 10, "COND worklist");
 463
 464   /* Prime the COND_EXPR worklist by placing all the COND_EXPRs on the
 465      worklist.  */
 466   FOR_EACH_BB (bb)
 467     {
 468       tree last = last_stmt (bb);
 469       if (last && TREE_CODE (last) == COND_EXPR)
 470         VARRAY_PUSH_TREE (cond_worklist, last);
 471     }
 472
 473   while (VARRAY_ACTIVE_SIZE (cond_worklist) > 0)
 474     {
 475       /* First get a list of all the interesting COND_EXPRs and potential
 476          single use variables which feed those COND_EXPRs.  This will drain
 477          COND_WORKLIST and initialize VARS_WORKLIST.  */
 478       record_single_argument_cond_exprs (cond_worklist, &vars_worklist, vars);
 479
 480       if (VARRAY_ACTIVE_SIZE (vars_worklist) > 0)
 481         {
 482           /* Now compute immediate uses for all the variables we care about.  */
 483           compute_immediate_uses (TDFA_USE_OPS, need_imm_uses_for);
 484
 485           /* We've computed immediate uses, so we can/must clear the VARS
 486              bitmap for the next iteration.  */
 487           bitmap_clear (vars);
 488
 489           /* And optimize.  This will drain VARS_WORKLIST and initialize
 490              COND_WORKLIST for the next iteration.  */
 491           substitute_single_use_vars (&cond_worklist, vars_worklist);
 492
 493           /* We do not incrementally update the dataflow information
 494              so we must free it here and recompute the necessary bits
 495              on the next iteration.  If this turns out to be expensive,
 496              methods for incrementally updating the dataflow are known.  */
 497           free_df ();
 498         }
 499     }
 500
 501   /* All done.  Clean up.  */
 502   BITMAP_XFREE (vars);
 503 }
 504
 505
 506 static bool
 507 gate_forwprop (void)
 508 {
 509   return 1;
 510 }
 511
 512 struct tree_opt_pass pass_forwprop = {
 513   "forwprop",                   /* name */
 514   gate_forwprop,                /* gate */
 515   tree_ssa_forward_propagate_single_use_vars,   /* execute */
 516   NULL,                         /* sub */
 517   NULL,                         /* next */
 518   0,                            /* static_pass_number */
 519   TV_TREE_FORWPROP,             /* tv_id */
 520   PROP_cfg | PROP_ssa,          /* properties_required */
 521   0,                            /* properties_provided */
 522   0,                            /* properties_destroyed */
 523   0,                            /* todo_flags_start */
 524   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 525   | TODO_verify_ssa
 526 };