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 void tree_ssa_forward_propagate_single_use_vars (void);
 117 static void record_single_argument_cond_exprs (varray_type,
 118                                                varray_type *,
 119                                                bitmap);
 120 static void substitute_single_use_vars (varray_type *, varray_type);
 121
 122 /* Find all COND_EXPRs with a condition that is a naked SSA_NAME or
 123    an equality comparison against a constant.
 124
 125    Record the identified COND_EXPRs and the SSA_NAME used in the COND_EXPR
 126    into a virtual array, which is returned to the caller.  Also record
 127    into VARS that we will need immediate uses for the identified SSA_NAME.
 128
 129    The more uninteresting COND_EXPRs and associated SSA_NAMEs we can
 130    filter out here, the faster this pass will run since its runtime is
 131    dominated by the time to build immediate uses.  */
 132
 133 static void
 134 record_single_argument_cond_exprs (varray_type cond_worklist,
 135                                    varray_type *vars_worklist,
 136                                    bitmap vars)
 137
 138 {
 139   /* The first pass over the blocks gathers the set of variables we need
 140      immediate uses for as well as the set of interesting COND_EXPRs.
 141
 142      A simpler implementation may be appropriate if/when we have a lower
 143      overhead means of getting immediate use information.  */
 144   while (VARRAY_ACTIVE_SIZE (cond_worklist) > 0)
 145     {
 146       tree last = VARRAY_TOP_TREE (cond_worklist);
 147
 148       VARRAY_POP (cond_worklist);
 149
 150       /* See if this block ends in a COND_EXPR.  */
 151       if (last && TREE_CODE (last) == COND_EXPR)
 152         {
 153           tree cond = COND_EXPR_COND (last);
 154           enum tree_code cond_code = TREE_CODE (cond);
 155
 156           /* If the condition is a lone variable or an equality test of
 157              an SSA_NAME against an integral constant, then we may have an
 158              optimizable case.
 159
 160              Note these conditions also ensure the COND_EXPR has no
 161              virtual operands or other side effects.  */
 162           if (cond_code == SSA_NAME
 163               || ((cond_code == EQ_EXPR || cond_code == NE_EXPR)
 164                   && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
 165                   && CONSTANT_CLASS_P (TREE_OPERAND (cond, 1))
 166                   && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
 167             {
 168               tree def;
 169               tree test_var;
 170
 171               /* Extract the single variable used in the test into TEST_VAR.  */
 172               if (cond_code == SSA_NAME)
 173                 test_var = cond;
 174               else
 175                 test_var = TREE_OPERAND (cond, 0);
 176
 177               /* If we have already recorded this SSA_NAME as interesting,
 178                  do not do so again.  */
 179               if (bitmap_bit_p (vars, SSA_NAME_VERSION (test_var)))
 180                 continue;
 181
 182               /* Now get the defining statement for TEST_VAR and see if it
 183                  something we are interested in.  */
 184               def = SSA_NAME_DEF_STMT (test_var);
 185               if (TREE_CODE (def) == MODIFY_EXPR)
 186                 {
 187                   tree def_rhs = TREE_OPERAND (def, 1);
 188
 189                   /* If TEST_VAR is set by adding or subtracting a constant
 190                      from an SSA_NAME, then it is interesting to us as we
 191                      can adjust the constant in the conditional and thus
 192                      eliminate the arithmetic operation.  */
 193                   if (TREE_CODE (def_rhs) == PLUS_EXPR
 194                          || TREE_CODE (def_rhs) == MINUS_EXPR)
 195                     {
 196                       tree op0 = TREE_OPERAND (def_rhs, 0);
 197                       tree op1 = TREE_OPERAND (def_rhs, 1);
 198
 199                       /* The first operand must be an SSA_NAME and the second
 200                          operand must be a constant.  */
 201                       if (TREE_CODE (op0) != SSA_NAME
 202                           || !CONSTANT_CLASS_P (op1)
 203                           || !INTEGRAL_TYPE_P (TREE_TYPE (op1)))
 204                         continue;
 205
 206                       /* Don't propagate if the first operand occurs in
 207                          an abnormal PHI.  */
 208                       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
 209                         continue;
 210                     }
 211
 212                   /* These cases require comparisons of a naked SSA_NAME or
 213                      comparison of an SSA_NAME against zero or one.  */
 214                   else if (TREE_CODE (cond) == SSA_NAME
 215                            || integer_zerop (TREE_OPERAND (cond, 1))
 216                            || integer_onep (TREE_OPERAND (cond, 1)))
 217                     {
 218                       /* If TEST_VAR is set from a relational operation
 219                          between two SSA_NAMEs or a combination of an SSA_NAME
 220                          and a constant, then it is interesting.  */
 221                       if (COMPARISON_CLASS_P (def_rhs))
 222                         {
 223                           tree op0 = TREE_OPERAND (def_rhs, 0);
 224                           tree op1 = TREE_OPERAND (def_rhs, 1);
 225
 226                           /* Both operands of DEF_RHS must be SSA_NAMEs or
 227                              constants.  */
 228                           if ((TREE_CODE (op0) != SSA_NAME
 229                                && !is_gimple_min_invariant (op0))
 230                               || (TREE_CODE (op1) != SSA_NAME
 231                                   && !is_gimple_min_invariant (op1)))
 232                             continue;
 233
 234                           /* Don't propagate if the first operand occurs in
 235                              an abnormal PHI.  */
 236                           if (TREE_CODE (op0) == SSA_NAME
 237                               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
 238                             continue;
 239
 240                           /* Don't propagate if the second operand occurs in
 241                              an abnormal PHI.  */
 242                           if (TREE_CODE (op1) == SSA_NAME
 243                               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))
 244                             continue;
 245                         }
 246
 247                       /* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it
 248                          is interesting.  */
 249                       else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR)
 250                         {
 251                           def_rhs = TREE_OPERAND (def_rhs, 0);
 252
 253                           /* DEF_RHS must be an SSA_NAME or constant.  */
 254                           if (TREE_CODE (def_rhs) != SSA_NAME
 255                               && !is_gimple_min_invariant (def_rhs))
 256                             continue;
 257
 258                           /* Don't propagate if the operand occurs in
 259                              an abnormal PHI.  */
 260                           if (TREE_CODE (def_rhs) == SSA_NAME
 261                               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_rhs))
 262                             continue;
 263                         }
 264
 265                       /* If TEST_VAR was set from a cast of an integer type
 266                          to a boolean type or a cast of a boolean to an
 267                          integral, then it is interesting.  */
 268                       else if (TREE_CODE (def_rhs) == NOP_EXPR
 269                                || TREE_CODE (def_rhs) == CONVERT_EXPR)
 270                         {
 271                           tree outer_type;
 272                           tree inner_type;
 273
 274                           outer_type = TREE_TYPE (def_rhs);
 275                           inner_type = TREE_TYPE (TREE_OPERAND (def_rhs, 0));
 276
 277                           if ((TREE_CODE (outer_type) == BOOLEAN_TYPE
 278                                && INTEGRAL_TYPE_P (inner_type))
 279                               || (TREE_CODE (inner_type) == BOOLEAN_TYPE
 280                                   && INTEGRAL_TYPE_P (outer_type)))
 281                             ;
 282                           else
 283                             continue;
 284
 285                           /* Don't propagate if the operand occurs in
 286                              an abnormal PHI.  */
 287                           if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
 288                               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND
 289                                                                   (def_rhs, 0)))
 290                             continue;
 291                         }
 292                       else
 293                         continue;
 294                     }
 295                   else
 296                     continue;
 297
 298                   /* All the tests passed, record TEST_VAR as interesting.  */
 299                   VARRAY_PUSH_TREE (*vars_worklist, test_var);
 300                   bitmap_set_bit (vars, SSA_NAME_VERSION (test_var));
 301                 }
 302             }
 303         }
 304     }
 305 }
 306
 307 /* Given FORWPROP_DATA containing SSA_NAMEs which are used in COND_EXPRs
 308    that we may be able to optimize, attempt to rewrite the condition
 309    in each COND_EXPR to use the RHS of the statement which defines the
 310    SSA_NAME used in the COND_EXPR.  */
 311
 312 static void
 313 substitute_single_use_vars (varray_type *cond_worklist,
 314                             varray_type vars_worklist)
 315 {
 316   use_operand_p use_p;
 317   while (VARRAY_ACTIVE_SIZE (vars_worklist) > 0)
 318     {
 319       tree test_var = VARRAY_TOP_TREE (vars_worklist);
 320       tree def_stmt = SSA_NAME_DEF_STMT (test_var);
 321       tree def;
 322       int num_uses, propagated_uses;
 323       imm_use_iterator imm_iter;
 324
 325       VARRAY_POP (vars_worklist);
 326
 327       propagated_uses = 0;
 328       num_uses = 0;
 329
 330       if (NUM_DEFS (STMT_DEF_OPS (def_stmt)) != 1)
 331         continue;
 332
 333       def = DEF_OP (STMT_DEF_OPS (def_stmt), 0);
 334
 335       /* If TEST_VAR is used more than once and is not a boolean set
 336          via TRUTH_NOT_EXPR with another SSA_NAME as its argument, then
 337          we can not optimize.  */
 338       if (has_single_use (def)
 339           || (TREE_CODE (TREE_TYPE (test_var)) == BOOLEAN_TYPE
 340               && TREE_CODE (TREE_OPERAND (def_stmt, 1)) == TRUTH_NOT_EXPR
 341               && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (def_stmt, 1), 0))
 342                   == SSA_NAME)))
 343         ;
 344       else
 345         continue;
 346
 347       /* Walk over each use and try to forward propagate the RHS of
 348          DEF into the use.  */
 349       FOR_EACH_IMM_USE_SAFE (use_p, imm_iter, def)
 350         {
 351           tree cond_stmt;
 352           tree cond;
 353           enum tree_code cond_code;
 354           tree def_rhs;
 355           enum tree_code def_rhs_code;
 356           tree new_cond;
 357
 358           cond_stmt = USE_STMT (use_p);
 359           num_uses++;
 360
 361           /* For now we can only propagate into COND_EXPRs.  */
 362           if (TREE_CODE (cond_stmt) != COND_EXPR)
 363             continue;
 364
 365           cond = COND_EXPR_COND (cond_stmt);
 366           cond_code = TREE_CODE (cond);
 367           def_rhs = TREE_OPERAND (def_stmt, 1);
 368           def_rhs_code = TREE_CODE (def_rhs);
 369
 370           /* If the definition of the single use variable was from an
 371              arithmetic operation, then we just need to adjust the
 372              constant in the COND_EXPR_COND and update the variable tested.  */
 373           if (def_rhs_code == PLUS_EXPR || def_rhs_code == MINUS_EXPR)
 374             {
 375               tree op0 = TREE_OPERAND (def_rhs, 0);
 376               tree op1 = TREE_OPERAND (def_rhs, 1);
 377               enum tree_code new_code;
 378               tree t;
 379
 380               /* If the variable was defined via X + C, then we must subtract
 381                  C from the constant in the conditional.  Otherwise we add
 382                  C to the constant in the conditional.  The result must fold
 383                  into a valid gimple operand to be optimizable.  */
 384               new_code = def_rhs_code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR;
 385               t = int_const_binop (new_code, TREE_OPERAND (cond, 1), op1, 0);
 386               if (!is_gimple_val (t))
 387                 continue;
 388
 389               new_cond = build (cond_code, boolean_type_node, op0, t);
 390             }
 391           /* If the variable is defined by a conditional expression... */
 392           else if (TREE_CODE_CLASS (def_rhs_code) == tcc_comparison)
 393             {
 394               /* TEST_VAR was set from a relational operator.  */
 395               tree op0 = TREE_OPERAND (def_rhs, 0);
 396               tree op1 = TREE_OPERAND (def_rhs, 1);
 397
 398               new_cond = build (def_rhs_code, boolean_type_node, op0, op1);
 399
 400               /* Invert the conditional if necessary.  */
 401               if ((cond_code == EQ_EXPR
 402                    && integer_zerop (TREE_OPERAND (cond, 1)))
 403                   || (cond_code == NE_EXPR
 404                       && integer_onep (TREE_OPERAND (cond, 1))))
 405                 {
 406                   new_cond = invert_truthvalue (new_cond);
 407
 408                   /* If we did not get a simple relational expression or
 409                      bare SSA_NAME, then we can not optimize this case.  */
 410                   if (!COMPARISON_CLASS_P (new_cond)
 411                       && TREE_CODE (new_cond) != SSA_NAME)
 412                     continue;
 413                 }
 414             }
 415           else
 416             {
 417               bool invert = false;
 418               enum tree_code new_code;
 419               tree new_arg;
 420
 421               /* TEST_VAR was set from a TRUTH_NOT_EXPR or a NOP_EXPR.  */
 422               if (def_rhs_code == TRUTH_NOT_EXPR)
 423                 invert = true;
 424
 425               if (cond_code == SSA_NAME
 426                   || (cond_code == NE_EXPR
 427                       && integer_zerop (TREE_OPERAND (cond, 1)))
 428                   || (cond_code == EQ_EXPR
 429                       && integer_onep (TREE_OPERAND (cond, 1))))
 430                 new_code = NE_EXPR;
 431               else
 432                 new_code = EQ_EXPR;
 433
 434               if (invert)
 435                 new_code = (new_code == EQ_EXPR ? NE_EXPR  : EQ_EXPR);
 436
 437               new_arg = TREE_OPERAND (def_rhs, 0);
 438               new_cond = build2 (new_code, boolean_type_node, new_arg,
 439                                  fold_convert (TREE_TYPE (new_arg),
 440                                                integer_zero_node));
 441             }
 442
 443           /* Dump details.  */
 444           if (dump_file && (dump_flags & TDF_DETAILS))
 445             {
 446               fprintf (dump_file, "  Replaced '");
 447               print_generic_expr (dump_file, cond, dump_flags);
 448               fprintf (dump_file, "' with '");
 449               print_generic_expr (dump_file, new_cond, dump_flags);
 450               fprintf (dump_file, "'\n");
 451             }
 452
 453           /* Replace the condition.  */
 454           COND_EXPR_COND (cond_stmt) = new_cond;
 455           update_stmt (cond_stmt);
 456           propagated_uses++;
 457           VARRAY_PUSH_TREE (*cond_worklist, cond_stmt);
 458         }
 459
 460       /* If we propagated into all the uses, then we can delete DEF.
 461          Unfortunately, we have to find the defining statement in
 462          whatever block it might be in.  */
 463       if (num_uses && num_uses == propagated_uses)
 464         {
 465           block_stmt_iterator bsi = bsi_for_stmt (def_stmt);
 466           bsi_remove (&bsi);
 467         }
 468     }
 469 }
 470
 471 /* Main entry point for the forward propagation optimizer.  */
 472
 473 static void
 474 tree_ssa_forward_propagate_single_use_vars (void)
 475 {
 476   basic_block bb;
 477   varray_type vars_worklist, cond_worklist;
 478
 479   vars = BITMAP_ALLOC (NULL);
 480   VARRAY_TREE_INIT (vars_worklist, 10, "VARS worklist");
 481   VARRAY_TREE_INIT (cond_worklist, 10, "COND worklist");
 482
 483   /* Prime the COND_EXPR worklist by placing all the COND_EXPRs on the
 484      worklist.  */
 485   FOR_EACH_BB (bb)
 486     {
 487       tree last = last_stmt (bb);
 488       if (last && TREE_CODE (last) == COND_EXPR)
 489         VARRAY_PUSH_TREE (cond_worklist, last);
 490     }
 491
 492   while (VARRAY_ACTIVE_SIZE (cond_worklist) > 0)
 493     {
 494       /* First get a list of all the interesting COND_EXPRs and potential
 495          single use variables which feed those COND_EXPRs.  This will drain
 496          COND_WORKLIST and initialize VARS_WORKLIST.  */
 497       record_single_argument_cond_exprs (cond_worklist, &vars_worklist, vars);
 498
 499       if (VARRAY_ACTIVE_SIZE (vars_worklist) > 0)
 500         {
 501           /* We've computed immediate uses, so we can/must clear the VARS
 502              bitmap for the next iteration.  */
 503           bitmap_clear (vars);
 504
 505           /* And optimize.  This will drain VARS_WORKLIST and initialize
 506              COND_WORKLIST for the next iteration.  */
 507           substitute_single_use_vars (&cond_worklist, vars_worklist);
 508         }
 509     }
 510
 511   /* All done.  Clean up.  */
 512   BITMAP_FREE (vars);
 513 }
 514
 515
 516 static bool
 517 gate_forwprop (void)
 518 {
 519   return 1;
 520 }
 521
 522 struct tree_opt_pass pass_forwprop = {
 523   "forwprop",                   /* name */
 524   gate_forwprop,                /* gate */
 525   tree_ssa_forward_propagate_single_use_vars,   /* execute */
 526   NULL,                         /* sub */
 527   NULL,                         /* next */
 528   0,                            /* static_pass_number */
 529   TV_TREE_FORWPROP,             /* tv_id */
 530   PROP_cfg | PROP_ssa
 531     | PROP_alias,               /* properties_required */
 532   0,                            /* properties_provided */
 533   0,                            /* properties_destroyed */
 534   0,                            /* todo_flags_start */
 535   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 536   | TODO_verify_ssa,
 537   0                                     /* letter */
 538 };