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           tree op0 = TREE_OPERAND (def_rhs, 0);
 193           tree op1 = TREE_OPERAND (def_rhs, 1);
 194           enum tree_code new_code;
 195           tree t;
 196
 197           /* If the variable was defined via X + C, then we must
 198              subtract C from the constant in the conditional.
 199              Otherwise we add C to the constant in the
 200              conditional.  The result must fold into a valid
 201              gimple operand to be optimizable.  */
 202           new_code = (TREE_CODE (def_rhs) == PLUS_EXPR
 203                       ? MINUS_EXPR : PLUS_EXPR);
 204           t = int_const_binop (new_code, TREE_OPERAND (cond, 1), op1, 0);
 205           if (!is_gimple_val (t))
 206             return NULL_TREE;
 207
 208           new_cond = build (cond_code, boolean_type_node, op0, t);
 209         }
 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             return NULL_TREE;
 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             return NULL_TREE;
 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             return NULL_TREE;
 245
 246           if (has_single_use (test_var))
 247             {
 248               /* TEST_VAR was set from a relational operator.  */
 249               tree op0 = TREE_OPERAND (def_rhs, 0);
 250               tree op1 = TREE_OPERAND (def_rhs, 1);
 251
 252               new_cond = build (TREE_CODE (def_rhs),
 253                                 boolean_type_node, op0, op1);
 254
 255               /* Invert the conditional if necessary.  */
 256               if ((cond_code == EQ_EXPR
 257                    && integer_zerop (TREE_OPERAND (cond, 1)))
 258                   || (cond_code == NE_EXPR
 259                       && integer_onep (TREE_OPERAND (cond, 1))))
 260                 {
 261                   new_cond = invert_truthvalue (new_cond);
 262
 263                   /* If we did not get a simple relational
 264                      expression or bare SSA_NAME, then we can
 265                      not optimize this case.  */
 266                   if (!COMPARISON_CLASS_P (new_cond)
 267                       && TREE_CODE (new_cond) != SSA_NAME)
 268                     new_cond = NULL_TREE;
 269                 }
 270             }
 271         }
 272
 273       /* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it
 274          is interesting.  */
 275       else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR)
 276         {
 277           enum tree_code new_code;
 278
 279           def_rhs = TREE_OPERAND (def_rhs, 0);
 280
 281           /* DEF_RHS must be an SSA_NAME or constant.  */
 282           if (TREE_CODE (def_rhs) != SSA_NAME
 283               && !is_gimple_min_invariant (def_rhs))
 284             return NULL_TREE;
 285
 286           /* Don't propagate if the operand occurs in
 287              an abnormal PHI.  */
 288           if (TREE_CODE (def_rhs) == SSA_NAME
 289               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def_rhs))
 290             return NULL_TREE;
 291
 292           if (cond_code == SSA_NAME
 293               || (cond_code == NE_EXPR
 294                   && integer_zerop (TREE_OPERAND (cond, 1)))
 295               || (cond_code == EQ_EXPR
 296                   && integer_onep (TREE_OPERAND (cond, 1))))
 297             new_code = EQ_EXPR;
 298           else
 299             new_code = NE_EXPR;
 300
 301           new_cond = build2 (new_code, boolean_type_node, def_rhs,
 302                              fold_convert (TREE_TYPE (def_rhs),
 303                                            integer_zero_node));
 304         }
 305
 306       /* If TEST_VAR was set from a cast of an integer type
 307          to a boolean type or a cast of a boolean to an
 308          integral, then it is interesting.  */
 309       else if (TREE_CODE (def_rhs) == NOP_EXPR
 310                || TREE_CODE (def_rhs) == CONVERT_EXPR)
 311         {
 312           tree outer_type;
 313           tree inner_type;
 314
 315           outer_type = TREE_TYPE (def_rhs);
 316           inner_type = TREE_TYPE (TREE_OPERAND (def_rhs, 0));
 317
 318           if ((TREE_CODE (outer_type) == BOOLEAN_TYPE
 319                && INTEGRAL_TYPE_P (inner_type))
 320               || (TREE_CODE (inner_type) == BOOLEAN_TYPE
 321                   && INTEGRAL_TYPE_P (outer_type)))
 322             ;
 323           else if (INTEGRAL_TYPE_P (outer_type)
 324                    && INTEGRAL_TYPE_P (inner_type)
 325                    && TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
 326                    && ssa_name_defined_by_comparison_p (TREE_OPERAND (def_rhs,
 327                                                                       0)))
 328             ;
 329           else
 330             return NULL_TREE;
 331
 332           /* Don't propagate if the operand occurs in
 333              an abnormal PHI.  */
 334           if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == SSA_NAME
 335               && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (TREE_OPERAND
 336                                                   (def_rhs, 0)))
 337             return NULL_TREE;
 338
 339           if (has_single_use (test_var))
 340             {
 341               enum tree_code new_code;
 342               tree new_arg;
 343
 344               if (cond_code == SSA_NAME
 345                   || (cond_code == NE_EXPR
 346                       && integer_zerop (TREE_OPERAND (cond, 1)))
 347                   || (cond_code == EQ_EXPR
 348                       && integer_onep (TREE_OPERAND (cond, 1))))
 349                 new_code = NE_EXPR;
 350               else
 351                 new_code = EQ_EXPR;
 352
 353               new_arg = TREE_OPERAND (def_rhs, 0);
 354               new_cond = build2 (new_code, boolean_type_node, new_arg,
 355                                  fold_convert (TREE_TYPE (new_arg),
 356                                                integer_zero_node));
 357             }
 358         }
 359     }
 360
 361   *test_var_p = test_var;
 362   return new_cond;
 363 }
 364
 365 /* Forward propagate a single-use variable into COND_EXPR as many
 366    times as possible.  */
 367
 368 static void
 369 forward_propagate_into_cond (tree cond_expr)
 370 {
 371   gcc_assert (TREE_CODE (cond_expr) == COND_EXPR);
 372
 373   while (1)
 374     {
 375       tree test_var = NULL_TREE;
 376       tree cond = COND_EXPR_COND (cond_expr);
 377       tree new_cond = forward_propagate_into_cond_1 (cond, &test_var);
 378
 379       /* Return if unsuccessful.  */
 380       if (new_cond == NULL_TREE)
 381         break;
 382
 383       /* Dump details.  */
 384       if (dump_file && (dump_flags & TDF_DETAILS))
 385         {
 386           fprintf (dump_file, "  Replaced '");
 387           print_generic_expr (dump_file, cond, dump_flags);
 388           fprintf (dump_file, "' with '");
 389           print_generic_expr (dump_file, new_cond, dump_flags);
 390           fprintf (dump_file, "'\n");
 391         }
 392
 393       COND_EXPR_COND (cond_expr) = new_cond;
 394       update_stmt (cond_expr);
 395
 396       if (has_zero_uses (test_var))
 397         {
 398           tree def = SSA_NAME_DEF_STMT (test_var);
 399           block_stmt_iterator bsi = bsi_for_stmt (def);
 400           bsi_remove (&bsi);
 401         }
 402     }
 403 }
 404
 405 /* Main entry point for the forward propagation optimizer.  */
 406
 407 static void
 408 tree_ssa_forward_propagate_single_use_vars (void)
 409 {
 410   basic_block bb;
 411
 412   FOR_EACH_BB (bb)
 413     {
 414       tree last = last_stmt (bb);
 415       if (last && TREE_CODE (last) == COND_EXPR)
 416         forward_propagate_into_cond (last);
 417     }
 418 }
 419
 420
 421 static bool
 422 gate_forwprop (void)
 423 {
 424   return 1;
 425 }
 426
 427 struct tree_opt_pass pass_forwprop = {
 428   "forwprop",                   /* name */
 429   gate_forwprop,                /* gate */
 430   tree_ssa_forward_propagate_single_use_vars,   /* execute */
 431   NULL,                         /* sub */
 432   NULL,                         /* next */
 433   0,                            /* static_pass_number */
 434   TV_TREE_FORWPROP,             /* tv_id */
 435   PROP_cfg | PROP_ssa
 436     | PROP_alias,               /* properties_required */
 437   0,                            /* properties_provided */
 438   0,                            /* properties_destroyed */
 439   0,                            /* todo_flags_start */
 440   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 441   | TODO_verify_ssa,
 442   0                                     /* letter */
 443 };