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 /* Forward propagate a single-use variable into COND once.  Return a
 113    new condition if successful.  Return NULL_TREE otherwise.  */
 114
 115 static tree
 116 forward_propagate_into_cond_1 (tree cond, tree *test_var_p)
 117 {
 118   tree new_cond = NULL_TREE;
 119   enum tree_code cond_code = TREE_CODE (cond);
 120   tree test_var = NULL_TREE;
 121   tree def;
 122   tree def_rhs;
 123
 124   /* If the condition is not a lone variable or an equality test of an
 125      SSA_NAME against an integral constant, then we do not have an
 126      optimizable case.
 127
 128      Note these conditions also ensure the COND_EXPR has no
 129      virtual operands or other side effects.  */
 130   if (cond_code != SSA_NAME
 131       && !((cond_code == EQ_EXPR || cond_code == NE_EXPR)
 132            && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
 133            && CONSTANT_CLASS_P (TREE_OPERAND (cond, 1))
 134            && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
 135     return NULL_TREE;
 136
 137   /* Extract the single variable used in the test into TEST_VAR.  */
 138   if (cond_code == SSA_NAME)
 139     test_var = cond;
 140   else
 141     test_var = TREE_OPERAND (cond, 0);
 142
 143   /* Now get the defining statement for TEST_VAR.  Skip this case if
 144      it's not defined by some MODIFY_EXPR.  */
 145   def = SSA_NAME_DEF_STMT (test_var);
 146   if (TREE_CODE (def) != MODIFY_EXPR)
 147     return NULL_TREE;
 148
 149   def_rhs = TREE_OPERAND (def, 1);
 150
 151   /* If TEST_VAR is set by adding or subtracting a constant
 152      from an SSA_NAME, then it is interesting to us as we
 153      can adjust the constant in the conditional and thus
 154      eliminate the arithmetic operation.  */
 155   if (TREE_CODE (def_rhs) == PLUS_EXPR
 156       || TREE_CODE (def_rhs) == MINUS_EXPR)
 157     {
 158       tree op0 = TREE_OPERAND (def_rhs, 0);
 159       tree op1 = TREE_OPERAND (def_rhs, 1);
 160
 161       /* The first operand must be an SSA_NAME and the second
 162          operand must be a constant.  */
 163       if (TREE_CODE (op0) != SSA_NAME
 164           || !CONSTANT_CLASS_P (op1)
 165           || !INTEGRAL_TYPE_P (TREE_TYPE (op1)))
 166         return NULL_TREE;
 167
 168       /* Don't propagate if the first operand occurs in
 169          an abnormal PHI.  */
 170       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
 171         return NULL_TREE;
 172
 173       if (has_single_use (test_var))
 174         {
 175           tree op0 = TREE_OPERAND (def_rhs, 0);
 176           tree op1 = TREE_OPERAND (def_rhs, 1);
 177           enum tree_code new_code;
 178           tree t;
 179
 180           /* If the variable was defined via X + C, then we must
 181              subtract C from the constant in the conditional.
 182              Otherwise we add C to the constant in the
 183              conditional.  The result must fold into a valid
 184              gimple operand to be optimizable.  */
 185           new_code = (TREE_CODE (def_rhs) == PLUS_EXPR
 186                       ? MINUS_EXPR : PLUS_EXPR);
 187           t = int_const_binop (new_code, TREE_OPERAND (cond, 1), op1, 0);
 188           if (!is_gimple_val (t))
 189             return NULL_TREE;
 190
 191           new_cond = build (cond_code, boolean_type_node, op0, t);
 192         }
 193     }
 194
 195   /* These cases require comparisons of a naked SSA_NAME or
 196      comparison of an SSA_NAME against zero or one.  */
 197   else if (TREE_CODE (cond) == SSA_NAME
 198            || integer_zerop (TREE_OPERAND (cond, 1))
 199            || integer_onep (TREE_OPERAND (cond, 1)))
 200     {
 201       /* If TEST_VAR is set from a relational operation
 202          between two SSA_NAMEs or a combination of an SSA_NAME
 203          and a constant, then it is interesting.  */
 204       if (COMPARISON_CLASS_P (def_rhs))
 205         {
 206           tree op0 = TREE_OPERAND (def_rhs, 0);
 207           tree op1 = TREE_OPERAND (def_rhs, 1);
 208
 209           /* Both operands of DEF_RHS must be SSA_NAMEs or
 210              constants.  */
 211           if ((TREE_CODE (op0) != SSA_NAME
 212                && !is_gimple_min_invariant (op0))
 213               || (TREE_CODE (op1) != SSA_NAME
 214                   && !is_gimple_min_invariant (op1)))
 215             return NULL_TREE;
 216
 217           /* Don't propagate if the first operand occurs in
 218              an abnormal PHI.  */
 219           if (TREE_CODE (op0) == SSA_NAME
 220               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0))
 221             return NULL_TREE;
 222
 223           /* Don't propagate if the second operand occurs in
 224              an abnormal PHI.  */
 225           if (TREE_CODE (op1) == SSA_NAME
 226               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))
 227             return NULL_TREE;
 228
 229           if (has_single_use (test_var))
 230             {
 231               /* TEST_VAR was set from a relational operator.  */
 232               tree op0 = TREE_OPERAND (def_rhs, 0);
 233               tree op1 = TREE_OPERAND (def_rhs, 1);
 234
 235               new_cond = build (TREE_CODE (def_rhs),
 236                                 boolean_type_node, op0, op1);
 237
 238               /* Invert the conditional if necessary.  */
 239               if ((cond_code == EQ_EXPR
 240                    && integer_zerop (TREE_OPERAND (cond, 1)))
 241                   || (cond_code == NE_EXPR
 242                       && integer_onep (TREE_OPERAND (cond, 1))))
 243                 {
 244                   new_cond = invert_truthvalue (new_cond);
 245
 246                   /* If we did not get a simple relational
 247                      expression or bare SSA_NAME, then we can
 248                      not optimize this case.  */
 249                   if (!COMPARISON_CLASS_P (new_cond)
 250                       && TREE_CODE (new_cond) != SSA_NAME)
 251                     new_cond = NULL_TREE;
 252                 }
 253             }
 254         }
 255
 256       /* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it
 257          is interesting.  */
 258       else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR)
 259         {
 260           enum tree_code new_code;
 261
 262           def_rhs = TREE_OPERAND (def_rhs, 0);
 263
 264           /* DEF_RHS must be an SSA_NAME or constant.  */
 265           if (TREE_CODE (def_rhs) != SSA_NAME
 266               && !is_gimple_min_invariant (def_rhs))
 267             return NULL_TREE;
 268
 269           /* Don't propagate if the operand occurs in
 270              an abnormal PHI.  */
 271           if (TREE_CODE (def_rhs) == SSA_NAME
 272               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_rhs))
 273             return NULL_TREE;
 274
 275           if (cond_code == SSA_NAME
 276               || (cond_code == NE_EXPR
 277                   && integer_zerop (TREE_OPERAND (cond, 1)))
 278               || (cond_code == EQ_EXPR
 279                   && integer_onep (TREE_OPERAND (cond, 1))))
 280             new_code = EQ_EXPR;
 281           else
 282             new_code = NE_EXPR;
 283
 284           new_cond = build2 (new_code, boolean_type_node, def_rhs,
 285                              fold_convert (TREE_TYPE (def_rhs),
 286                                            integer_zero_node));
 287         }
 288
 289       /* If TEST_VAR was set from a cast of an integer type
 290          to a boolean type or a cast of a boolean to an
 291          integral, then it is interesting.  */
 292       else if (TREE_CODE (def_rhs) == NOP_EXPR
 293                || TREE_CODE (def_rhs) == CONVERT_EXPR)
 294         {
 295           tree outer_type;
 296           tree inner_type;
 297
 298           outer_type = TREE_TYPE (def_rhs);
 299           inner_type = TREE_TYPE (TREE_OPERAND (def_rhs, 0));
 300
 301           if ((TREE_CODE (outer_type) == BOOLEAN_TYPE
 302                && INTEGRAL_TYPE_P (inner_type))
 303               || (TREE_CODE (inner_type) == BOOLEAN_TYPE
 304                   && INTEGRAL_TYPE_P (outer_type)))
 305             ;
 306           else
 307             return NULL_TREE;
 308
 309           /* Don't propagate if the operand occurs in
 310              an abnormal PHI.  */
 311           if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
 312               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND
 313                                                   (def_rhs, 0)))
 314             return NULL_TREE;
 315
 316           if (has_single_use (test_var))
 317             {
 318               enum tree_code new_code;
 319               tree new_arg;
 320
 321               if (cond_code == SSA_NAME
 322                   || (cond_code == NE_EXPR
 323                       && integer_zerop (TREE_OPERAND (cond, 1)))
 324                   || (cond_code == EQ_EXPR
 325                       && integer_onep (TREE_OPERAND (cond, 1))))
 326                 new_code = NE_EXPR;
 327               else
 328                 new_code = EQ_EXPR;
 329
 330               new_arg = TREE_OPERAND (def_rhs, 0);
 331               new_cond = build2 (new_code, boolean_type_node, new_arg,
 332                                  fold_convert (TREE_TYPE (new_arg),
 333                                                integer_zero_node));
 334             }
 335         }
 336     }
 337
 338   *test_var_p = test_var;
 339   return new_cond;
 340 }
 341
 342 /* Forward propagate a single-use variable into COND_EXPR as many
 343    times as possible.  */
 344
 345 static void
 346 forward_propagate_into_cond (tree cond_expr)
 347 {
 348   gcc_assert (TREE_CODE (cond_expr) == COND_EXPR);
 349
 350   while (1)
 351     {
 352       tree test_var = NULL_TREE;
 353       tree cond = COND_EXPR_COND (cond_expr);
 354       tree new_cond = forward_propagate_into_cond_1 (cond, &test_var);
 355
 356       /* Return if unsuccessful.  */
 357       if (new_cond == NULL_TREE)
 358         break;
 359
 360       /* Dump details.  */
 361       if (dump_file && (dump_flags & TDF_DETAILS))
 362         {
 363           fprintf (dump_file, "  Replaced '");
 364           print_generic_expr (dump_file, cond, dump_flags);
 365           fprintf (dump_file, "' with '");
 366           print_generic_expr (dump_file, new_cond, dump_flags);
 367           fprintf (dump_file, "'\n");
 368         }
 369
 370       COND_EXPR_COND (cond_expr) = new_cond;
 371       update_stmt (cond_expr);
 372
 373       if (has_zero_uses (test_var))
 374         {
 375           tree def = SSA_NAME_DEF_STMT (test_var);
 376           block_stmt_iterator bsi = bsi_for_stmt (def);
 377           bsi_remove (&bsi);
 378         }
 379     }
 380 }
 381
 382 /* Main entry point for the forward propagation optimizer.  */
 383
 384 static void
 385 tree_ssa_forward_propagate_single_use_vars (void)
 386 {
 387   basic_block bb;
 388
 389   FOR_EACH_BB (bb)
 390     {
 391       tree last = last_stmt (bb);
 392       if (last && TREE_CODE (last) == COND_EXPR)
 393         forward_propagate_into_cond (last);
 394     }
 395 }
 396
 397
 398 static bool
 399 gate_forwprop (void)
 400 {
 401   return 1;
 402 }
 403
 404 struct tree_opt_pass pass_forwprop = {
 405   "forwprop",                   /* name */
 406   gate_forwprop,                /* gate */
 407   tree_ssa_forward_propagate_single_use_vars,   /* execute */
 408   NULL,                         /* sub */
 409   NULL,                         /* next */
 410   0,                            /* static_pass_number */
 411   TV_TREE_FORWPROP,             /* tv_id */
 412   PROP_cfg | PROP_ssa
 413     | PROP_alias,               /* properties_required */
 414   0,                            /* properties_provided */
 415   0,                            /* properties_destroyed */
 416   0,                            /* todo_flags_start */
 417   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 418   | TODO_verify_ssa,
 419   0                                     /* letter */
 420 };