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