gcc/tree-ssa-threadedge.c

   1 /* SSA Jump Threading
   2    Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
   3    Contributed by Jeff Law  <law@redhat.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "flags.h"
  27 #include "rtl.h"
  28 #include "tm_p.h"
  29 #include "ggc.h"
  30 #include "basic-block.h"
  31 #include "cfgloop.h"
  32 #include "output.h"
  33 #include "expr.h"
  34 #include "function.h"
  35 #include "diagnostic.h"
  36 #include "timevar.h"
  37 #include "tree-dump.h"
  38 #include "tree-flow.h"
  39 #include "domwalk.h"
  40 #include "real.h"
  41 #include "tree-pass.h"
  42 #include "tree-ssa-propagate.h"
  43 #include "langhooks.h"
  44 #include "params.h"
  45
  46 /* To avoid code explosion due to jump threading, we limit the
  47    number of statements we are going to copy.  This variable
  48    holds the number of statements currently seen that we'll have
  49    to copy as part of the jump threading process.  */
  50 static int stmt_count;
  51
  52 /* Return TRUE if we may be able to thread an incoming edge into
  53    BB to an outgoing edge from BB.  Return FALSE otherwise.  */
  54
  55 bool
  56 potentially_threadable_block (basic_block bb)
  57 {
  58   block_stmt_iterator bsi;
  59
  60   /* If BB has a single successor or a single predecessor, then
  61      there is no threading opportunity.  */
  62   if (single_succ_p (bb) || single_pred_p (bb))
  63     return false;
  64
  65   /* If BB does not end with a conditional, switch or computed goto,
  66      then there is no threading opportunity.  */
  67   bsi = bsi_last (bb);
  68   if (bsi_end_p (bsi)
  69       || ! bsi_stmt (bsi)
  70       || (TREE_CODE (bsi_stmt (bsi)) != COND_EXPR
  71           && TREE_CODE (bsi_stmt (bsi)) != GOTO_EXPR
  72           && TREE_CODE (bsi_stmt (bsi)) != SWITCH_EXPR))
  73     return false;
  74
  75   return true;
  76 }
  77
  78 /* Return the LHS of any ASSERT_EXPR where OP appears as the first
  79    argument to the ASSERT_EXPR and in which the ASSERT_EXPR dominates
  80    BB.  If no such ASSERT_EXPR is found, return OP.  */
  81
  82 static tree
  83 lhs_of_dominating_assert (tree op, basic_block bb, tree stmt)
  84 {
  85   imm_use_iterator imm_iter;
  86   tree use_stmt;
  87   use_operand_p use_p;
  88
  89   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, op)
  90     {
  91       use_stmt = USE_STMT (use_p);
  92       if (use_stmt != stmt
  93           && TREE_CODE (use_stmt) == MODIFY_EXPR
  94           && TREE_CODE (TREE_OPERAND (use_stmt, 1)) == ASSERT_EXPR
  95           && TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 0) == op
  96           && dominated_by_p (CDI_DOMINATORS, bb, bb_for_stmt (use_stmt)))
  97         {
  98           return TREE_OPERAND (use_stmt, 0);
  99         }
 100     }
 101   return op;
 102 }
 103
 104
 105 /* We record temporary equivalences created by PHI nodes or
 106    statements within the target block.  Doing so allows us to
 107    identify more jump threading opportunities, even in blocks
 108    with side effects.
 109
 110    We keep track of those temporary equivalences in a stack
 111    structure so that we can unwind them when we're done processing
 112    a particular edge.  This routine handles unwinding the data
 113    structures.  */
 114
 115 static void
 116 remove_temporary_equivalences (VEC(tree, heap) **stack)
 117 {
 118   while (VEC_length (tree, *stack) > 0)
 119     {
 120       tree prev_value, dest;
 121
 122       dest = VEC_pop (tree, *stack);
 123
 124       /* A NULL value indicates we should stop unwinding, otherwise
 125          pop off the next entry as they're recorded in pairs.  */
 126       if (dest == NULL)
 127         break;
 128
 129       prev_value = VEC_pop (tree, *stack);
 130       SSA_NAME_VALUE (dest) = prev_value;
 131     }
 132 }
 133
 134 /* Record a temporary equivalence, saving enough information so that
 135    we can restore the state of recorded equivalences when we're
 136    done processing the current edge.  */
 137
 138 static void
 139 record_temporary_equivalence (tree x, tree y, VEC(tree, heap) **stack)
 140 {
 141   tree prev_x = SSA_NAME_VALUE (x);
 142
 143   if (TREE_CODE (y) == SSA_NAME)
 144     {
 145       tree tmp = SSA_NAME_VALUE (y);
 146       y = tmp ? tmp : y;
 147     }
 148
 149   SSA_NAME_VALUE (x) = y;
 150   VEC_reserve (tree, heap, *stack, 2);
 151   VEC_quick_push (tree, *stack, prev_x);
 152   VEC_quick_push (tree, *stack, x);
 153 }
 154
 155 /* Record temporary equivalences created by PHIs at the target of the
 156    edge E.  Record unwind information for the equivalences onto STACK.
 157
 158    If a PHI which prevents threading is encountered, then return FALSE
 159    indicating we should not thread this edge, else return TRUE.  */
 160
 161 static bool
 162 record_temporary_equivalences_from_phis (edge e, VEC(tree, heap) **stack)
 163 {
 164   tree phi;
 165
 166   /* Each PHI creates a temporary equivalence, record them.
 167      These are context sensitive equivalences and will be removed
 168      later.  */
 169   for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
 170     {
 171       tree src = PHI_ARG_DEF_FROM_EDGE (phi, e);
 172       tree dst = PHI_RESULT (phi);
 173
 174       /* If the desired argument is not the same as this PHI's result
 175          and it is set by a PHI in E->dest, then we can not thread
 176          through E->dest.  */
 177       if (src != dst
 178           && TREE_CODE (src) == SSA_NAME
 179           && TREE_CODE (SSA_NAME_DEF_STMT (src)) == PHI_NODE
 180           && bb_for_stmt (SSA_NAME_DEF_STMT (src)) == e->dest)
 181         return false;
 182
 183       /* We consider any non-virtual PHI as a statement since it
 184          count result in a constant assignment or copy operation.  */
 185       if (is_gimple_reg (dst))
 186         stmt_count++;
 187
 188       record_temporary_equivalence (dst, src, stack);
 189     }
 190   return true;
 191 }
 192
 193 /* Try to simplify each statement in E->dest, ultimately leading to
 194    a simplification of the COND_EXPR at the end of E->dest.
 195
 196    Record unwind information for temporary equivalences onto STACK.
 197
 198    Use SIMPLIFY (a pointer to a callback function) to further simplify
 199    statements using pass specific information.
 200
 201    We might consider marking just those statements which ultimately
 202    feed the COND_EXPR.  It's not clear if the overhead of bookkeeping
 203    would be recovered by trying to simplify fewer statements.
 204
 205    If we are able to simplify a statement into the form
 206    SSA_NAME = (SSA_NAME | gimple invariant), then we can record
 207    a context sensitive equivalency which may help us simplify
 208    later statements in E->dest.  */
 209
 210 static tree
 211 record_temporary_equivalences_from_stmts_at_dest (edge e,
 212                                                   VEC(tree, heap) **stack,
 213                                                   tree (*simplify) (tree,
 214                                                                     tree))
 215 {
 216   block_stmt_iterator bsi;
 217   tree stmt = NULL;
 218   int max_stmt_count;
 219
 220   max_stmt_count = PARAM_VALUE (PARAM_MAX_JUMP_THREAD_DUPLICATION_STMTS);
 221
 222   /* Walk through each statement in the block recording equivalences
 223      we discover.  Note any equivalences we discover are context
 224      sensitive (ie, are dependent on traversing E) and must be unwound
 225      when we're finished processing E.  */
 226   for (bsi = bsi_start (e->dest); ! bsi_end_p (bsi); bsi_next (&bsi))
 227     {
 228       tree cached_lhs = NULL;
 229
 230       stmt = bsi_stmt (bsi);
 231
 232       /* Ignore empty statements and labels.  */
 233       if (IS_EMPTY_STMT (stmt) || TREE_CODE (stmt) == LABEL_EXPR)
 234         continue;
 235
 236       /* If the statement has volatile operands, then we assume we
 237          can not thread through this block.  This is overly
 238          conservative in some ways.  */
 239       if (TREE_CODE (stmt) == ASM_EXPR && ASM_VOLATILE_P (stmt))
 240         return NULL;
 241
 242       /* If duplicating this block is going to cause too much code
 243          expansion, then do not thread through this block.  */
 244       stmt_count++;
 245       if (stmt_count > max_stmt_count)
 246         return NULL;
 247
 248       /* If this is not a MODIFY_EXPR which sets an SSA_NAME to a new
 249          value, then do not try to simplify this statement as it will
 250          not simplify in any way that is helpful for jump threading.  */
 251       if (TREE_CODE (stmt) != MODIFY_EXPR
 252           || TREE_CODE (TREE_OPERAND (stmt, 0)) != SSA_NAME)
 253         continue;
 254
 255       /* At this point we have a statement which assigns an RHS to an
 256          SSA_VAR on the LHS.  We want to try and simplify this statement
 257          to expose more context sensitive equivalences which in turn may
 258          allow us to simplify the condition at the end of the loop.
 259
 260          Handle simple copy operations as well as implied copies from
 261          ASSERT_EXPRs.  */
 262       if (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)
 263         cached_lhs = TREE_OPERAND (stmt, 1);
 264       else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ASSERT_EXPR)
 265         cached_lhs = TREE_OPERAND (TREE_OPERAND (stmt, 1), 0);
 266       else
 267         {
 268           /* A statement that is not a trivial copy or ASSERT_EXPR.
 269              We're going to temporarily copy propagate the operands
 270              and see if that allows us to simplify this statement.  */
 271           tree *copy, pre_fold_expr;
 272           ssa_op_iter iter;
 273           use_operand_p use_p;
 274           unsigned int num, i = 0;
 275
 276           num = NUM_SSA_OPERANDS (stmt, (SSA_OP_USE | SSA_OP_VUSE));
 277           copy = XCNEWVEC (tree, num);
 278
 279           /* Make a copy of the uses & vuses into USES_COPY, then cprop into
 280              the operands.  */
 281           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
 282             {
 283               tree tmp = NULL;
 284               tree use = USE_FROM_PTR (use_p);
 285
 286               copy[i++] = use;
 287               if (TREE_CODE (use) == SSA_NAME)
 288                 tmp = SSA_NAME_VALUE (use);
 289               if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)
 290                 SET_USE (use_p, tmp);
 291             }
 292
 293           /* Try to fold/lookup the new expression.  Inserting the
 294              expression into the hash table is unlikely to help
 295              Sadly, we have to handle conditional assignments specially
 296              here, because fold expects all the operands of an expression
 297              to be folded before the expression itself is folded, but we
 298              can't just substitute the folded condition here.  */
 299           if (TREE_CODE (TREE_OPERAND (stmt, 1)) == COND_EXPR)
 300             {
 301               tree cond = COND_EXPR_COND (TREE_OPERAND (stmt, 1));
 302               cond = fold (cond);
 303               if (cond == boolean_true_node)
 304                 pre_fold_expr = COND_EXPR_THEN (TREE_OPERAND (stmt, 1));
 305               else if (cond == boolean_false_node)
 306                 pre_fold_expr = COND_EXPR_ELSE (TREE_OPERAND (stmt, 1));
 307               else
 308                 pre_fold_expr = TREE_OPERAND (stmt, 1);
 309             }
 310           else
 311             pre_fold_expr = TREE_OPERAND (stmt, 1);
 312
 313           if (pre_fold_expr)
 314             {
 315               cached_lhs = fold (pre_fold_expr);
 316               if (TREE_CODE (cached_lhs) != SSA_NAME
 317                   && !is_gimple_min_invariant (cached_lhs))
 318                 cached_lhs = (*simplify) (stmt, stmt);
 319             }
 320
 321           /* Restore the statement's original uses/defs.  */
 322           i = 0;
 323           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
 324             SET_USE (use_p, copy[i++]);
 325
 326           free (copy);
 327         }
 328
 329       /* Record the context sensitive equivalence if we were able
 330          to simplify this statement.  */
 331       if (cached_lhs
 332           && (TREE_CODE (cached_lhs) == SSA_NAME
 333               || is_gimple_min_invariant (cached_lhs)))
 334         record_temporary_equivalence (TREE_OPERAND (stmt, 0),
 335                                       cached_lhs,
 336                                       stack);
 337     }
 338   return stmt;
 339 }
 340
 341 /* Simplify the control statement at the end of the block E->dest.
 342
 343    To avoid allocating memory unnecessarily, a scratch COND_EXPR
 344    is available to use/clobber in DUMMY_COND.
 345
 346    Use SIMPLIFY (a pointer to a callback function) to further simplify
 347    a condition using pass specific information.
 348
 349    Return the simplified condition or NULL if simplification could
 350    not be performed.  */
 351
 352 static tree
 353 simplify_control_stmt_condition (edge e,
 354                                  tree stmt,
 355                                  tree dummy_cond,
 356                                  tree (*simplify) (tree, tree),
 357                                  bool handle_dominating_asserts)
 358 {
 359   tree cond, cached_lhs;
 360
 361   if (TREE_CODE (stmt) == COND_EXPR)
 362     cond = COND_EXPR_COND (stmt);
 363   else if (TREE_CODE (stmt) == GOTO_EXPR)
 364     cond = GOTO_DESTINATION (stmt);
 365   else
 366     cond = SWITCH_COND (stmt);
 367
 368   /* For comparisons, we have to update both operands, then try
 369      to simplify the comparison.  */
 370   if (COMPARISON_CLASS_P (cond))
 371     {
 372       tree op0, op1;
 373       enum tree_code cond_code;
 374
 375       op0 = TREE_OPERAND (cond, 0);
 376       op1 = TREE_OPERAND (cond, 1);
 377       cond_code = TREE_CODE (cond);
 378
 379       /* Get the current value of both operands.  */
 380       if (TREE_CODE (op0) == SSA_NAME)
 381         {
 382           tree tmp = SSA_NAME_VALUE (op0);
 383           if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)
 384             op0 = tmp;
 385         }
 386
 387       if (TREE_CODE (op1) == SSA_NAME)
 388         {
 389           tree tmp = SSA_NAME_VALUE (op1);
 390           if (tmp && TREE_CODE (tmp) != VALUE_HANDLE)
 391             op1 = tmp;
 392         }
 393
 394       if (handle_dominating_asserts)
 395         {
 396           /* Now see if the operand was consumed by an ASSERT_EXPR
 397              which dominates E->src.  If so, we want to replace the
 398              operand with the LHS of the ASSERT_EXPR.  */
 399           if (TREE_CODE (op0) == SSA_NAME)
 400             op0 = lhs_of_dominating_assert (op0, e->src, stmt);
 401
 402           if (TREE_CODE (op1) == SSA_NAME)
 403             op1 = lhs_of_dominating_assert (op1, e->src, stmt);
 404         }
 405
 406       /* We may need to canonicalize the comparison.  For
 407          example, op0 might be a constant while op1 is an
 408          SSA_NAME.  Failure to canonicalize will cause us to
 409          miss threading opportunities.  */
 410       if (cond_code != SSA_NAME
 411           && tree_swap_operands_p (op0, op1, false))
 412         {
 413           tree tmp;
 414           cond_code = swap_tree_comparison (TREE_CODE (cond));
 415           tmp = op0;
 416           op0 = op1;
 417           op1 = tmp;
 418         }
 419
 420       /* Stuff the operator and operands into our dummy conditional
 421          expression.  */
 422       TREE_SET_CODE (COND_EXPR_COND (dummy_cond), cond_code);
 423       TREE_OPERAND (COND_EXPR_COND (dummy_cond), 0) = op0;
 424       TREE_OPERAND (COND_EXPR_COND (dummy_cond), 1) = op1;
 425
 426       /* We absolutely do not care about any type conversions
 427          we only care about a zero/nonzero value.  */
 428       fold_defer_overflow_warnings ();
 429
 430       cached_lhs = fold (COND_EXPR_COND (dummy_cond));
 431       while (TREE_CODE (cached_lhs) == NOP_EXPR
 432              || TREE_CODE (cached_lhs) == CONVERT_EXPR
 433              || TREE_CODE (cached_lhs) == NON_LVALUE_EXPR)
 434         cached_lhs = TREE_OPERAND (cached_lhs, 0);
 435
 436       fold_undefer_overflow_warnings (is_gimple_min_invariant (cached_lhs),
 437                                       stmt, WARN_STRICT_OVERFLOW_CONDITIONAL);
 438
 439       /* If we have not simplified the condition down to an invariant,
 440          then use the pass specific callback to simplify the condition.  */
 441       if (! is_gimple_min_invariant (cached_lhs))
 442         cached_lhs = (*simplify) (dummy_cond, stmt);
 443     }
 444
 445   /* We can have conditionals which just test the state of a variable
 446      rather than use a relational operator.  These are simpler to handle.  */
 447   else if (TREE_CODE (cond) == SSA_NAME)
 448     {
 449       cached_lhs = cond;
 450
 451       /* Get the variable's current value from the equivalency chains.
 452
 453          It is possible to get loops in the SSA_NAME_VALUE chains
 454          (consider threading the backedge of a loop where we have
 455          a loop invariant SSA_NAME used in the condition.  */
 456       if (cached_lhs
 457           && TREE_CODE (cached_lhs) == SSA_NAME
 458           && SSA_NAME_VALUE (cached_lhs))
 459         cached_lhs = SSA_NAME_VALUE (cached_lhs);
 460
 461       /* If we're dominated by a suitable ASSERT_EXPR, then
 462          update CACHED_LHS appropriately.  */
 463       if (handle_dominating_asserts && TREE_CODE (cached_lhs) == SSA_NAME)
 464         cached_lhs = lhs_of_dominating_assert (cached_lhs, e->src, stmt);
 465
 466       /* If we haven't simplified to an invariant yet, then use the
 467          pass specific callback to try and simplify it further.  */
 468       if (cached_lhs && ! is_gimple_min_invariant (cached_lhs))
 469         cached_lhs = (*simplify) (stmt, stmt);
 470     }
 471   else
 472     cached_lhs = NULL;
 473
 474   return cached_lhs;
 475 }
 476
 477 /* We are exiting E->src, see if E->dest ends with a conditional
 478    jump which has a known value when reached via E.
 479
 480    Special care is necessary if E is a back edge in the CFG as we
 481    may have already recorded equivalences for E->dest into our
 482    various tables, including the result of the conditional at
 483    the end of E->dest.  Threading opportunities are severely
 484    limited in that case to avoid short-circuiting the loop
 485    incorrectly.
 486
 487    Note it is quite common for the first block inside a loop to
 488    end with a conditional which is either always true or always
 489    false when reached via the loop backedge.  Thus we do not want
 490    to blindly disable threading across a loop backedge.  */
 491
 492 void
 493 thread_across_edge (tree dummy_cond,
 494                     edge e,
 495                     bool handle_dominating_asserts,
 496                     VEC(tree, heap) **stack,
 497                     tree (*simplify) (tree, tree))
 498 {
 499   tree stmt;
 500
 501   /* If E is a backedge, then we want to verify that the COND_EXPR,
 502      SWITCH_EXPR or GOTO_EXPR at the end of e->dest is not affected
 503      by any statements in e->dest.  If it is affected, then it is not
 504      safe to thread this edge.  */
 505   if (e->flags & EDGE_DFS_BACK)
 506     {
 507       ssa_op_iter iter;
 508       use_operand_p use_p;
 509       tree last = bsi_stmt (bsi_last (e->dest));
 510
 511       FOR_EACH_SSA_USE_OPERAND (use_p, last, iter, SSA_OP_USE | SSA_OP_VUSE)
 512         {
 513           tree use = USE_FROM_PTR (use_p);
 514
 515           if (TREE_CODE (use) == SSA_NAME
 516               && TREE_CODE (SSA_NAME_DEF_STMT (use)) != PHI_NODE
 517               && bb_for_stmt (SSA_NAME_DEF_STMT (use)) == e->dest)
 518             goto fail;
 519         }
 520     }
 521
 522   stmt_count = 0;
 523
 524   /* PHIs create temporary equivalences.  */
 525   if (!record_temporary_equivalences_from_phis (e, stack))
 526     goto fail;
 527
 528   /* Now walk each statement recording any context sensitive
 529      temporary equivalences we can detect.  */
 530   stmt = record_temporary_equivalences_from_stmts_at_dest (e, stack, simplify);
 531   if (!stmt)
 532     goto fail;
 533
 534   /* If we stopped at a COND_EXPR or SWITCH_EXPR, see if we know which arm
 535      will be taken.  */
 536   if (TREE_CODE (stmt) == COND_EXPR
 537       || TREE_CODE (stmt) == GOTO_EXPR
 538       || TREE_CODE (stmt) == SWITCH_EXPR)
 539     {
 540       tree cond;
 541
 542       /* Extract and simplify the condition.  */
 543       cond = simplify_control_stmt_condition (e, stmt, dummy_cond, simplify, handle_dominating_asserts);
 544
 545       if (cond && is_gimple_min_invariant (cond))
 546         {
 547           edge taken_edge = find_taken_edge (e->dest, cond);
 548           basic_block dest = (taken_edge ? taken_edge->dest : NULL);
 549
 550           if (dest == e->dest)
 551             goto fail;
 552
 553           remove_temporary_equivalences (stack);
 554           register_jump_thread (e, taken_edge);
 555         }
 556     }
 557
 558  fail:
 559   remove_temporary_equivalences (stack);
 560 }