gcc/tree-ssa-threadbackward.c

   1 /* SSA Jump Threading
   2    Copyright (C) 2005-2015 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 3, 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 COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "backend.h"
  24 #include "predict.h"
  25 #include "tree.h"
  26 #include "gimple.h"
  27 #include "fold-const.h"
  28 #include "cfgloop.h"
  29 #include "gimple-iterator.h"
  30 #include "tree-cfg.h"
  31 #include "tree-ssa-threadupdate.h"
  32 #include "params.h"
  33 #include "tree-ssa-loop.h"
  34 #include "cfganal.h"
  35 #include "tree-pass.h"
  36
  37 static int max_threaded_paths;
  38
  39 /* Simple helper to get the last statement from BB, which is assumed
  40    to be a control statement.   Return NULL if the last statement is
  41    not a control statement.  */
  42
  43 static gimple *
  44 get_gimple_control_stmt (basic_block bb)
  45 {
  46   gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
  47
  48   if (gsi_end_p (gsi))
  49     return NULL;
  50
  51   gimple *stmt = gsi_stmt (gsi);
  52   enum gimple_code code = gimple_code (stmt);
  53   if (code == GIMPLE_COND || code == GIMPLE_SWITCH || code == GIMPLE_GOTO)
  54     return stmt;
  55   return NULL;
  56 }
  57
  58 /* Return true if the CFG contains at least one path from START_BB to END_BB.
  59    When a path is found, record in PATH the blocks from END_BB to START_BB.
  60    VISITED_BBS is used to make sure we don't fall into an infinite loop.  Bound
  61    the recursion to basic blocks belonging to LOOP.  */
  62
  63 static bool
  64 fsm_find_thread_path (basic_block start_bb, basic_block end_bb,
  65                       vec<basic_block, va_gc> *&path,
  66                       hash_set<basic_block> *visited_bbs, loop_p loop)
  67 {
  68   if (loop != start_bb->loop_father)
  69     return false;
  70
  71   if (start_bb == end_bb)
  72     {
  73       vec_safe_push (path, start_bb);
  74       return true;
  75     }
  76
  77   if (!visited_bbs->add (start_bb))
  78     {
  79       edge e;
  80       edge_iterator ei;
  81       FOR_EACH_EDGE (e, ei, start_bb->succs)
  82         if (fsm_find_thread_path (e->dest, end_bb, path, visited_bbs, loop))
  83           {
  84             vec_safe_push (path, start_bb);
  85             return true;
  86           }
  87     }
  88
  89   return false;
  90 }
  91
  92 /* We trace the value of the SSA_NAME NAME back through any phi nodes looking
  93    for places where it gets a constant value and save the path.  Stop after
  94    having recorded MAX_PATHS jump threading paths.  */
  95
  96 static void
  97 fsm_find_control_statement_thread_paths (tree name,
  98                                          hash_set<basic_block> *visited_bbs,
  99                                          vec<basic_block, va_gc> *&path,
 100                                          bool seen_loop_phi)
 101 {
 102   gimple *def_stmt = SSA_NAME_DEF_STMT (name);
 103   basic_block var_bb = gimple_bb (def_stmt);
 104
 105   if (var_bb == NULL)
 106     return;
 107
 108   /* For the moment we assume that an SSA chain only contains phi nodes, and
 109      eventually one of the phi arguments will be an integer constant.  In the
 110      future, this could be extended to also handle simple assignments of
 111      arithmetic operations.  */
 112   if (gimple_code (def_stmt) != GIMPLE_PHI)
 113     return;
 114
 115   /* Avoid infinite recursion.  */
 116   if (visited_bbs->add (var_bb))
 117     return;
 118
 119   gphi *phi = as_a <gphi *> (def_stmt);
 120   int next_path_length = 0;
 121   basic_block last_bb_in_path = path->last ();
 122
 123   if (loop_containing_stmt (phi)->header == gimple_bb (phi))
 124     {
 125       /* Do not walk through more than one loop PHI node.  */
 126       if (seen_loop_phi)
 127         return;
 128       seen_loop_phi = true;
 129     }
 130
 131   /* Following the chain of SSA_NAME definitions, we jumped from a definition in
 132      LAST_BB_IN_PATH to a definition in VAR_BB.  When these basic blocks are
 133      different, append to PATH the blocks from LAST_BB_IN_PATH to VAR_BB.  */
 134   if (var_bb != last_bb_in_path)
 135     {
 136       edge e;
 137       int e_count = 0;
 138       edge_iterator ei;
 139       vec<basic_block, va_gc> *next_path;
 140       vec_alloc (next_path, n_basic_blocks_for_fn (cfun));
 141
 142       /* When VAR_BB == LAST_BB_IN_PATH, then the first block in the path
 143          will already be in VISITED_BBS.  When they are not equal, then we
 144          must ensure that first block is accounted for to ensure we do not
 145          create bogus jump threading paths.  */
 146       visited_bbs->add ((*path)[0]);
 147       FOR_EACH_EDGE (e, ei, last_bb_in_path->preds)
 148         {
 149           hash_set<basic_block> *visited_bbs = new hash_set<basic_block>;
 150
 151           if (fsm_find_thread_path (var_bb, e->src, next_path, visited_bbs,
 152                                     e->src->loop_father))
 153             ++e_count;
 154
 155           delete visited_bbs;
 156
 157           /* If there is more than one path, stop.  */
 158           if (e_count > 1)
 159             {
 160               vec_free (next_path);
 161               return;
 162             }
 163         }
 164
 165       /* Stop if we have not found a path: this could occur when the recursion
 166          is stopped by one of the bounds.  */
 167       if (e_count == 0)
 168         {
 169           vec_free (next_path);
 170           return;
 171         }
 172
 173       /* Make sure we haven't already visited any of the nodes in
 174          NEXT_PATH.  Don't add them here to avoid pollution.  */
 175       for (unsigned int i = 0; i < next_path->length () - 1; i++)
 176         {
 177           if (visited_bbs->contains ((*next_path)[i]))
 178             {
 179               vec_free (next_path);
 180               return;
 181             }
 182         }
 183
 184       /* Now add the nodes to VISISTED_BBS.  */
 185       for (unsigned int i = 0; i < next_path->length () - 1; i++)
 186         visited_bbs->add ((*next_path)[i]);
 187
 188       /* Append all the nodes from NEXT_PATH to PATH.  */
 189       vec_safe_splice (path, next_path);
 190       next_path_length = next_path->length ();
 191       vec_free (next_path);
 192     }
 193
 194   gcc_assert (path->last () == var_bb);
 195
 196   /* Iterate over the arguments of PHI.  */
 197   unsigned int i;
 198   for (i = 0; i < gimple_phi_num_args (phi); i++)
 199     {
 200       tree arg = gimple_phi_arg_def (phi, i);
 201       basic_block bbi = gimple_phi_arg_edge (phi, i)->src;
 202
 203       /* Skip edges pointing outside the current loop.  */
 204       if (!arg || var_bb->loop_father != bbi->loop_father)
 205         continue;
 206
 207       if (TREE_CODE (arg) == SSA_NAME)
 208         {
 209           vec_safe_push (path, bbi);
 210           /* Recursively follow SSA_NAMEs looking for a constant definition.  */
 211           fsm_find_control_statement_thread_paths (arg, visited_bbs, path,
 212                                                    seen_loop_phi);
 213
 214           path->pop ();
 215           continue;
 216         }
 217
 218       if (TREE_CODE (arg) != INTEGER_CST)
 219         continue;
 220
 221       int path_length = path->length ();
 222       if (path_length > PARAM_VALUE (PARAM_MAX_FSM_THREAD_LENGTH))
 223         {
 224           if (dump_file && (dump_flags & TDF_DETAILS))
 225             fprintf (dump_file, "FSM jump-thread path not considered: "
 226                      "the number of basic blocks on the path "
 227                      "exceeds PARAM_MAX_FSM_THREAD_LENGTH.\n");
 228           continue;
 229         }
 230
 231       if (max_threaded_paths <= 0)
 232         {
 233           if (dump_file && (dump_flags & TDF_DETAILS))
 234             fprintf (dump_file, "FSM jump-thread path not considered: "
 235                      "the number of previously recorded FSM paths to thread "
 236                      "exceeds PARAM_MAX_FSM_THREAD_PATHS.\n");
 237           continue;
 238         }
 239
 240       /* Add BBI to the path.  */
 241       vec_safe_push (path, bbi);
 242       ++path_length;
 243
 244       int n_insns = 0;
 245       gimple_stmt_iterator gsi;
 246       int j;
 247       loop_p loop = (*path)[0]->loop_father;
 248       bool path_crosses_loops = false;
 249
 250       /* Count the number of instructions on the path: as these instructions
 251          will have to be duplicated, we will not record the path if there are
 252          too many instructions on the path.  Also check that all the blocks in
 253          the path belong to a single loop.  */
 254       for (j = 1; j < path_length - 1; j++)
 255         {
 256           basic_block bb = (*path)[j];
 257
 258           if (bb->loop_father != loop)
 259             {
 260               path_crosses_loops = true;
 261               break;
 262             }
 263
 264           for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 265             {
 266               gimple *stmt = gsi_stmt (gsi);
 267               /* Do not count empty statements and labels.  */
 268               if (gimple_code (stmt) != GIMPLE_NOP
 269                   && gimple_code (stmt) != GIMPLE_LABEL
 270                   && !is_gimple_debug (stmt))
 271                 ++n_insns;
 272             }
 273         }
 274
 275       if (path_crosses_loops)
 276         {
 277           if (dump_file && (dump_flags & TDF_DETAILS))
 278             fprintf (dump_file, "FSM jump-thread path not considered: "
 279                      "the path crosses loops.\n");
 280           path->pop ();
 281           continue;
 282         }
 283
 284       if (n_insns >= PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATH_INSNS))
 285         {
 286           if (dump_file && (dump_flags & TDF_DETAILS))
 287             fprintf (dump_file, "FSM jump-thread path not considered: "
 288                      "the number of instructions on the path "
 289                      "exceeds PARAM_MAX_FSM_THREAD_PATH_INSNS.\n");
 290           path->pop ();
 291           continue;
 292         }
 293
 294       vec<jump_thread_edge *> *jump_thread_path
 295         = new vec<jump_thread_edge *> ();
 296
 297       /* Record the edges between the blocks in PATH.  */
 298       for (j = 0; j < path_length - 1; j++)
 299         {
 300           edge e = find_edge ((*path)[path_length - j - 1],
 301                               (*path)[path_length - j - 2]);
 302           gcc_assert (e);
 303           jump_thread_edge *x = new jump_thread_edge (e, EDGE_FSM_THREAD);
 304           jump_thread_path->safe_push (x);
 305         }
 306
 307       gimple *stmt = get_gimple_control_stmt ((*path)[0]);
 308       gcc_assert (stmt);
 309       /* We have found a constant value for ARG.  For GIMPLE_SWITCH
 310          and GIMPLE_GOTO, we use it as-is.  However, for a GIMPLE_COND
 311          we need to substitute, fold and simplify.  */
 312       if (gimple_code (stmt) == GIMPLE_COND)
 313         {
 314           enum tree_code cond_code = gimple_cond_code (stmt);
 315
 316           /* We know the underyling format of the condition.  */
 317           arg = fold_binary (cond_code, boolean_type_node,
 318                              arg, gimple_cond_rhs (stmt));
 319         }
 320
 321       /* Add the edge taken when the control variable has value ARG.  */
 322       edge taken_edge = find_taken_edge ((*path)[0], arg);
 323       jump_thread_edge *x
 324         = new jump_thread_edge (taken_edge, EDGE_NO_COPY_SRC_BLOCK);
 325       jump_thread_path->safe_push (x);
 326
 327       register_jump_thread (jump_thread_path);
 328       --max_threaded_paths;
 329
 330       /* Remove BBI from the path.  */
 331       path->pop ();
 332     }
 333
 334   /* Remove all the nodes that we added from NEXT_PATH.  */
 335   if (next_path_length)
 336     vec_safe_truncate (path, (path->length () - next_path_length));
 337 }
 338
 339 /* Search backwards from BB looking for paths where NAME (an SSA_NAME)
 340    is a constant.  Record such paths for jump threading.
 341
 342    It is assumed that BB ends with a control statement and that by
 343    finding a path where NAME is a constant, we can thread the path.  */
 344
 345 void
 346 find_jump_threads_backwards (edge e)
 347 {
 348   if (!flag_expensive_optimizations
 349       || optimize_function_for_size_p (cfun)
 350       || e->dest->loop_father != e->src->loop_father
 351       || loop_depth (e->dest->loop_father) == 0)
 352     return;
 353
 354   gimple *stmt = get_gimple_control_stmt (e->dest);
 355   if (!stmt)
 356     return;
 357
 358   enum gimple_code code = gimple_code (stmt);
 359   tree name = NULL;
 360   if (code == GIMPLE_SWITCH)
 361     name = gimple_switch_index (as_a <gswitch *> (stmt));
 362   else if (code == GIMPLE_GOTO)
 363     name = gimple_goto_dest (stmt);
 364   else if (code == GIMPLE_COND)
 365     {
 366       if (TREE_CODE (gimple_cond_lhs (stmt)) == SSA_NAME
 367           && TREE_CODE (gimple_cond_rhs (stmt)) == INTEGER_CST
 368           && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))
 369               || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))))
 370         name = gimple_cond_lhs (stmt);
 371     }
 372
 373   if (!name || TREE_CODE (name) != SSA_NAME)
 374     return;
 375
 376   vec<basic_block, va_gc> *bb_path;
 377   vec_alloc (bb_path, n_basic_blocks_for_fn (cfun));
 378   vec_safe_push (bb_path, e->dest);
 379   hash_set<basic_block> *visited_bbs = new hash_set<basic_block>;
 380
 381   max_threaded_paths = PARAM_VALUE (PARAM_MAX_FSM_THREAD_PATHS);
 382   fsm_find_control_statement_thread_paths (name, visited_bbs, bb_path, false);
 383
 384   delete visited_bbs;
 385   vec_free (bb_path);
 386 }