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    In addition to eliminating the variable and the statement which assigns
  84    a value to the variable, we may be able to later thread the jump without
  85    adding insane complexity in the dominator optimizer.
  86
  87    This will (of course) be extended as other needs arise.  */
  88
  89 /* Bitmap of variables for which we want immediate uses.  This is set
  90    by record_single_argument_cond_exprs and tested in need_imm_uses_for.  */
  91 static bitmap vars;
  92
  93 static bool need_imm_uses_for (tree);
  94 static void tree_ssa_forward_propagate_single_use_vars (void);
  95 static varray_type record_single_argument_cond_exprs (void);
  96 static void substitute_single_use_vars (varray_type);
  97
  98 /* Function indicating whether we ought to include information for 'var'
  99    when calculating immediate uses.  */
 100
 101 static bool
 102 need_imm_uses_for (tree var)
 103 {
 104   return bitmap_bit_p (vars, SSA_NAME_VERSION (var));
 105 }
 106
 107 /* Find all COND_EXPRs with a condition that is a naked SSA_NAME or
 108    an equality comparison against a constant.
 109
 110    Record the identified COND_EXPRs and the SSA_NAME used in the COND_EXPR
 111    into a virtual array, which is returned to the caller.  Also record
 112    into VARS that we will need immediate uses for the identified SSA_NAME.
 113
 114    The more uninteresting COND_EXPRs and associated SSA_NAMEs we can
 115    filter out here, the faster this pass will run since its runtime is
 116    dominated by the time to build immediate uses.  */
 117
 118 static varray_type
 119 record_single_argument_cond_exprs (void)
 120 {
 121   basic_block bb;
 122   varray_type retval;
 123
 124   vars = BITMAP_XMALLOC ();
 125
 126   VARRAY_TREE_INIT (retval, 10, "forward propagation vars");
 127
 128   /* The first pass over the blocks gathers the set of variables we need
 129      immediate uses for as well as the set of interesting COND_EXPRs.
 130
 131      A simpler implementation may be appropriate if/when we have a lower
 132      overhead means of getting immediate use information.  */
 133   FOR_EACH_BB (bb)
 134     {
 135       tree last = last_stmt (bb);
 136
 137       /* See if this block ends in a COND_EXPR.  */
 138       if (last && TREE_CODE (last) == COND_EXPR)
 139         {
 140           tree cond = COND_EXPR_COND (last);
 141           enum tree_code cond_code = TREE_CODE (cond);
 142
 143           /* If the condition is a lone variable or an equality test of
 144              an SSA_NAME against an integral constant, then we may have an
 145              optimizable case.
 146
 147              Note these conditions also ensure the COND_EXPR has no
 148              virtual operands or other side effects.  */
 149           if (cond_code == SSA_NAME
 150               || ((cond_code == EQ_EXPR || cond_code == NE_EXPR)
 151                   && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
 152                   && TREE_CODE_CLASS (TREE_CODE (TREE_OPERAND (cond, 1))) == 'c'
 153                   && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
 154             {
 155               tree def;
 156               tree test_var;
 157
 158               /* Extract the single variable used in the test into TEST_VAR.  */
 159               if (cond_code == SSA_NAME)
 160                 test_var = cond;
 161               else
 162                 test_var = TREE_OPERAND (cond, 0);
 163
 164               /* If we have already recorded this SSA_NAME as interesting,
 165                  do not do so again.  */
 166               if (bitmap_bit_p (vars, SSA_NAME_VERSION (test_var)))
 167                 continue;
 168
 169               /* Now get the defining statement for TEST_VAR and see if it
 170                  something we are interested in.  */
 171               def = SSA_NAME_DEF_STMT (test_var);
 172               if (TREE_CODE (def) == MODIFY_EXPR)
 173                 {
 174                   tree def_rhs = TREE_OPERAND (def, 1);
 175
 176                   /* If TEST_VAR is set by adding or subtracting a constant
 177                      from an SSA_NAME, then it is interesting to us as we
 178                      can adjust the constant in the conditional and thus
 179                      eliminate the arithmetic operation.  */
 180                   if (TREE_CODE (def_rhs) == PLUS_EXPR
 181                          || TREE_CODE (def_rhs) == MINUS_EXPR)
 182                     {
 183                       tree op0 = TREE_OPERAND (def_rhs, 0);
 184                       tree op1 = TREE_OPERAND (def_rhs, 1);
 185
 186                       /* The first operand must be an SSA_NAME and the second
 187                          operand must be a constant.  */
 188                       if (TREE_CODE (op0) != SSA_NAME
 189                           || TREE_CODE_CLASS (TREE_CODE (op1)) != 'c'
 190                           || !INTEGRAL_TYPE_P (TREE_TYPE (op1)))
 191                         continue;
 192                     }
 193
 194                   /* These cases require comparisons of a naked SSA_NAME or
 195                      comparison of an SSA_NAME against zero or one.  */
 196                   else if (TREE_CODE (cond) == SSA_NAME
 197                            || integer_zerop (TREE_OPERAND (cond, 1))
 198                            || integer_onep (TREE_OPERAND (cond, 1)))
 199                     {
 200                       /* If TEST_VAR is set from a relational operation
 201                          between two SSA_NAMEs or a combination of an SSA_NAME
 202                          and a constant, then it is interesting.  */
 203                       if (TREE_CODE_CLASS (TREE_CODE (def_rhs)) == '<')
 204                         {
 205                           tree op0 = TREE_OPERAND (def_rhs, 0);
 206                           tree op1 = TREE_OPERAND (def_rhs, 1);
 207
 208                           /* Both operands of DEF_RHS must be SSA_NAMEs or
 209                              constants.  */
 210                           if ((TREE_CODE (op0) != SSA_NAME
 211                                && !is_gimple_min_invariant (op0))
 212                               || (TREE_CODE (op1) != SSA_NAME
 213                                   && !is_gimple_min_invariant (op1)))
 214                             continue;
 215                         }
 216
 217                       /* If TEST_VAR is set from a TRUTH_NOT_EXPR, then it
 218                          is interesting.  */
 219                       else if (TREE_CODE (def_rhs) == TRUTH_NOT_EXPR)
 220                         {
 221                           def_rhs = TREE_OPERAND (def_rhs, 0);
 222
 223                           /* DEF_RHS must be an SSA_NAME or constant.  */
 224                           if (TREE_CODE (def_rhs) != SSA_NAME
 225                               && !is_gimple_min_invariant (def_rhs))
 226                             continue;
 227                         }
 228                       else
 229                         continue;
 230                     }
 231                   else
 232                     continue;
 233
 234                   /* All the tests passed, record TEST_VAR as interesting.  */
 235                   VARRAY_PUSH_TREE (retval, test_var);
 236                   bitmap_set_bit (vars, SSA_NAME_VERSION (test_var));
 237                 }
 238             }
 239         }
 240     }
 241   return retval;
 242 }
 243
 244 /* Given FORWPROP_DATA containing SSA_NAMEs which are used in COND_EXPRs
 245    that we may be able to optimize, attempt to rewrite the condition
 246    in each COND_EXPR to use the RHS of the statement which defines the
 247    SSA_NAME used in the COND_EXPR.  */
 248
 249 static void
 250 substitute_single_use_vars (varray_type forwprop_data)
 251 {
 252   unsigned int i;
 253
 254   for (i = 0; i < VARRAY_ACTIVE_SIZE (forwprop_data); i++)
 255     {
 256       tree test_var = VARRAY_TREE (forwprop_data, i);
 257       tree def = SSA_NAME_DEF_STMT (test_var);
 258       dataflow_t df;
 259       int j, num_uses, propagated_uses;
 260       block_stmt_iterator bsi;
 261
 262       /* Now compute the immediate uses of TEST_VAR.  */
 263       df = get_immediate_uses (def);
 264       num_uses = num_immediate_uses (df);
 265       propagated_uses = 0;
 266
 267       /* If TEST_VAR is used more than once and is not a boolean set
 268          via TRUTH_NOT_EXPR with another SSA_NAME as its argument, then
 269          we can not optimize.  */
 270       if (num_uses == 1
 271           || (TREE_CODE (TREE_TYPE (test_var)) == BOOLEAN_TYPE
 272               && TREE_CODE (TREE_OPERAND (def, 1)) == TRUTH_NOT_EXPR
 273               && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (def, 1), 0))
 274                   == SSA_NAME)))
 275         ;
 276       else
 277         continue;
 278
 279       /* Walk over each use and try to forward propagate the RHS of
 280          DEF into the use.  */
 281       for (j = 0; j < num_uses; j++)
 282         {
 283           tree cond_stmt;
 284           tree cond;
 285           enum tree_code cond_code;
 286           tree def_rhs;
 287           enum tree_code def_rhs_code;
 288           tree new_cond;
 289
 290           cond_stmt = immediate_use (df, j);
 291
 292           /* For now we can only propagate into COND_EXPRs.  */
 293           if (TREE_CODE (cond_stmt) != COND_EXPR)
 294             continue;
 295
 296           cond = COND_EXPR_COND (cond_stmt);
 297           cond_code = TREE_CODE (cond);
 298           def_rhs = TREE_OPERAND (def, 1);
 299           def_rhs_code = TREE_CODE (def_rhs);
 300
 301           /* If the definition of the single use variable was from an
 302              arithmetic operation, then we just need to adjust the
 303              constant in the COND_EXPR_COND and update the variable tested.  */
 304           if (def_rhs_code == PLUS_EXPR || def_rhs_code == MINUS_EXPR)
 305             {
 306               tree op0 = TREE_OPERAND (def_rhs, 0);
 307               tree op1 = TREE_OPERAND (def_rhs, 1);
 308               enum tree_code new_code;
 309               tree t;
 310
 311               /* If the variable was defined via X + C, then we must subtract
 312                  C from the constant in the conditional.  Otherwise we add
 313                  C to the constant in the conditional.  The result must fold
 314                  into a valid gimple operand to be optimizable.  */
 315               new_code = def_rhs_code == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR;
 316               t = int_const_binop (new_code, TREE_OPERAND (cond, 1), op1, 0);
 317               if (!is_gimple_val (t))
 318                 continue;
 319
 320               new_cond = build (cond_code, boolean_type_node, op0, t);
 321             }
 322           /* If the variable is defined by a conditional expression... */
 323           else if (TREE_CODE_CLASS (def_rhs_code) == '<')
 324             {
 325               /* TEST_VAR was set from a relational operator.  */
 326               tree op0 = TREE_OPERAND (def_rhs, 0);
 327               tree op1 = TREE_OPERAND (def_rhs, 1);
 328
 329               new_cond = build (def_rhs_code, boolean_type_node, op0, op1);
 330
 331               /* Invert the conditional if necessary.  */
 332               if ((cond_code == EQ_EXPR
 333                    && integer_zerop (TREE_OPERAND (cond, 1)))
 334                   || (cond_code == NE_EXPR
 335                       && integer_onep (TREE_OPERAND (cond, 1))))
 336                 {
 337                   new_cond = invert_truthvalue (new_cond);
 338
 339                   /* If we did not get a simple relational expression or
 340                      bare SSA_NAME, then we can not optimize this case.  */
 341                   if (TREE_CODE_CLASS (TREE_CODE (new_cond)) != '<'
 342                       && TREE_CODE (new_cond) != SSA_NAME)
 343                     continue;
 344                 }
 345             }
 346           else
 347             {
 348               /* TEST_VAR was set from a TRUTH_NOT_EXPR.  */
 349               if (cond_code == SSA_NAME
 350                   || (cond_code == NE_EXPR
 351                       && integer_zerop (TREE_OPERAND (cond, 1)))
 352                   || (cond_code == EQ_EXPR
 353                       && integer_onep (TREE_OPERAND (cond, 1))))
 354                 new_cond = build (EQ_EXPR, boolean_type_node,
 355                                   TREE_OPERAND (def_rhs, 0),
 356                                   convert (TREE_TYPE (def_rhs),
 357                                            integer_zero_node));
 358               else
 359                 new_cond = build (NE_EXPR, boolean_type_node,
 360                                   TREE_OPERAND (def_rhs, 0),
 361                                   convert (TREE_TYPE (def_rhs),
 362                                            integer_zero_node));
 363             }
 364
 365           /* Dump details.  */
 366           if (dump_file && (dump_flags & TDF_DETAILS))
 367             {
 368               fprintf (dump_file, "  Replaced '");
 369               print_generic_expr (dump_file, cond, dump_flags);
 370               fprintf (dump_file, "' with '");
 371               print_generic_expr (dump_file, new_cond, dump_flags);
 372               fprintf (dump_file, "'\n");
 373             }
 374
 375           /* Replace the condition.  */
 376           COND_EXPR_COND (cond_stmt) = new_cond;
 377           modify_stmt (cond_stmt);
 378           propagated_uses++;
 379         }
 380
 381       /* If we propagated into all the uses, then we can delete DEF.
 382          Unfortunately, we have to find the defining statement in
 383          whatever block it might be in.  */
 384       if (num_uses && num_uses == propagated_uses)
 385         for (bsi = bsi_start (bb_for_stmt (def));
 386              !bsi_end_p (bsi);
 387              bsi_next (&bsi))
 388           {
 389             if (def == bsi_stmt (bsi))
 390               {
 391                 bsi_remove (&bsi);
 392                 break;
 393               }
 394           }
 395     }
 396 }
 397
 398 /* Main entry point for the forward propagation optimizer.  */
 399
 400 static void
 401 tree_ssa_forward_propagate_single_use_vars (void)
 402 {
 403   varray_type forwprop_data;
 404
 405   /* First get a list of all the interesting COND_EXPRs and potential single
 406      use variables which feed those COND_EXPRs.  */
 407   forwprop_data = record_single_argument_cond_exprs ();
 408
 409   /* Now compute immediate uses for all the variables we care about.  */
 410   compute_immediate_uses (TDFA_USE_OPS, need_imm_uses_for);
 411
 412   /* We are done with the VARS bitmap and other dataflow information.  */
 413   BITMAP_XFREE (vars);
 414   vars = NULL;
 415
 416   /* And optimize.  */
 417   substitute_single_use_vars (forwprop_data);
 418
 419   /* All done.  Clean up.  */
 420   free_df ();
 421   VARRAY_CLEAR (forwprop_data);
 422 }
 423
 424
 425 static bool
 426 gate_forwprop (void)
 427 {
 428   return 1;
 429 }
 430
 431 struct tree_opt_pass pass_forwprop = {
 432   "forwprop",                   /* name */
 433   gate_forwprop,                /* gate */
 434   tree_ssa_forward_propagate_single_use_vars,   /* execute */
 435   NULL,                         /* sub */
 436   NULL,                         /* next */
 437   0,                            /* static_pass_number */
 438   TV_TREE_FORWPROP,             /* tv_id */
 439   PROP_cfg | PROP_ssa,          /* properties_required */
 440   0,                            /* properties_provided */
 441   0,                            /* properties_destroyed */
 442   0,                            /* todo_flags_start */
 443   TODO_dump_func | TODO_ggc_collect     /* todo_flags_finish */
 444   | TODO_verify_ssa
 445 };