gcc/tree-ssa-threadedge.c

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