nsz Git - libfirm/blob - ir/opt/jumpthreading.c

   1 /*
   2  * Copyright (C) 1995-2010 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Path-Sensitive Jump Threading
  23  * @date    10. Sep. 2006
  24  * @author  Christoph Mallon, Matthias Braun
  25  */
  26 #include "config.h"
  27
  28 #include "iroptimize.h"
  29
  30 #include <assert.h>
  31 #include <stdbool.h>
  32 #include "array_t.h"
  33 #include "debug.h"
  34 #include "ircons.h"
  35 #include "irgmod.h"
  36 #include "irgopt.h"
  37 #include "irgwalk.h"
  38 #include "irnode.h"
  39 #include "irnode_t.h"
  40 #include "iredges.h"
  41 #include "iredges_t.h"
  42 #include "irtools.h"
  43 #include "irgraph.h"
  44 #include "tv.h"
  45 #include "iroptimize.h"
  46 #include "iropt_dbg.h"
  47 #include "irpass.h"
  48 #include "vrp.h"
  49 #include "firmstat_t.h"
  50
  51 #undef AVOID_PHIB
  52
  53 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  54
  55 /**
  56  * Add the new predecessor x to node node, which is either a Block or a Phi
  57  */
  58 static void add_pred(ir_node* node, ir_node* x)
  59 {
  60         ir_node** ins;
  61         int n;
  62         int i;
  63
  64         assert(is_Block(node));
  65
  66         n = get_irn_arity(node);
  67         NEW_ARR_A(ir_node*, ins, n + 1);
  68         for (i = 0; i < n; i++)
  69                 ins[i] = get_irn_n(node, i);
  70         ins[n] = x;
  71         set_irn_in(node, n + 1, ins);
  72 }
  73
  74 static ir_node *ssa_second_def;
  75 static ir_node *ssa_second_def_block;
  76
  77 static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode,
  78                                            int first)
  79 {
  80         int i;
  81         int n_cfgpreds;
  82         ir_graph *irg;
  83         ir_node *phi;
  84         ir_node **in;
  85         ir_node *dummy;
  86
  87         /* In case of a bad input to a block we need to return the bad value */
  88         if (is_Bad(block)) {
  89                 ir_graph *irg = get_irn_irg(block);
  90                 return new_r_Bad(irg, mode);
  91         }
  92
  93         /* the other defs can't be marked for cases where a user of the original
  94          * value is in the same block as the alternative definition.
  95          * In this case we mustn't use the alternative definition.
  96          * So we keep a flag that indicated whether we walked at least 1 block
  97          * away and may use the alternative definition */
  98         if (block == ssa_second_def_block && !first) {
  99                 return ssa_second_def;
 100         }
 101
 102         /* already processed this block? */
 103         if (irn_visited(block)) {
 104                 ir_node *value = (ir_node*) get_irn_link(block);
 105                 return value;
 106         }
 107
 108         irg = get_irn_irg(block);
 109         assert(block != get_irg_start_block(irg));
 110
 111         /* a Block with only 1 predecessor needs no Phi */
 112         n_cfgpreds = get_Block_n_cfgpreds(block);
 113         if (n_cfgpreds == 1) {
 114                 ir_node *pred_block = get_Block_cfgpred_block(block, 0);
 115                 ir_node *value      = search_def_and_create_phis(pred_block, mode, 0);
 116
 117                 set_irn_link(block, value);
 118                 mark_irn_visited(block);
 119                 return value;
 120         }
 121
 122         /* create a new Phi */
 123         NEW_ARR_A(ir_node*, in, n_cfgpreds);
 124         dummy = new_r_Dummy(irg, mode);
 125         for (i = 0; i < n_cfgpreds; ++i)
 126                 in[i] = dummy;
 127
 128         phi = new_r_Phi(block, n_cfgpreds, in, mode);
 129         set_irn_link(block, phi);
 130         mark_irn_visited(block);
 131
 132         /* set Phi predecessors */
 133         for (i = 0; i < n_cfgpreds; ++i) {
 134                 ir_node *pred_block = get_Block_cfgpred_block(block, i);
 135                 ir_node *pred_val   = search_def_and_create_phis(pred_block, mode, 0);
 136
 137                 set_irn_n(phi, i, pred_val);
 138         }
 139
 140         return phi;
 141 }
 142
 143 /**
 144  * Given a set of values this function constructs SSA-form for the users of the
 145  * first value (the users are determined through the out-edges of the value).
 146  * Uses the irn_visited flags. Works without using the dominance tree.
 147  */
 148 static void construct_ssa(ir_node *orig_block, ir_node *orig_val,
 149                           ir_node *second_block, ir_node *second_val)
 150 {
 151         ir_graph *irg;
 152         ir_mode *mode;
 153
 154         /* no need to do anything */
 155         if (orig_val == second_val)
 156                 return;
 157
 158         irg = get_irn_irg(orig_val);
 159         inc_irg_visited(irg);
 160
 161         mode = get_irn_mode(orig_val);
 162         set_irn_link(orig_block, orig_val);
 163         mark_irn_visited(orig_block);
 164
 165         ssa_second_def_block = second_block;
 166         ssa_second_def       = second_val;
 167
 168         /* Only fix the users of the first, i.e. the original node */
 169         foreach_out_edge_safe(orig_val, edge) {
 170                 ir_node *user = get_edge_src_irn(edge);
 171                 int j = get_edge_src_pos(edge);
 172                 ir_node *user_block = get_nodes_block(user);
 173                 ir_node *newval;
 174
 175                 /* ignore keeps */
 176                 if (is_End(user))
 177                         continue;
 178
 179                 DB((dbg, LEVEL_3, ">>> Fixing user %+F (pred %d == %+F)\n", user, j, get_irn_n(user, j)));
 180
 181                 if (is_Phi(user)) {
 182                         ir_node *pred_block = get_Block_cfgpred_block(user_block, j);
 183                         newval = search_def_and_create_phis(pred_block, mode, 1);
 184                 } else {
 185                         newval = search_def_and_create_phis(user_block, mode, 1);
 186                 }
 187
 188                 /* don't fix newly created Phis from the SSA construction */
 189                 if (newval != user) {
 190                         DB((dbg, LEVEL_4, ">>>> Setting input %d of %+F to %+F\n", j, user, newval));
 191                         set_irn_n(user, j, newval);
 192                 }
 193         }
 194 }
 195
 196 /**
 197  * jumpthreading produces critical edges, e.g. B-C:
 198  *     A         A
 199  *  \ /       \  |
 200  *   B    =>   B |
 201  *  / \       / \|
 202  *     C         C
 203  *
 204  * By splitting this critical edge more threadings might be possible.
 205  */
 206 static void split_critical_edge(ir_node *block, int pos)
 207 {
 208         ir_graph *irg = get_irn_irg(block);
 209         ir_node *in[1];
 210         ir_node *new_block;
 211         ir_node *new_jmp;
 212
 213         in[0] = get_Block_cfgpred(block, pos);
 214         new_block = new_r_Block(irg, 1, in);
 215         new_jmp = new_r_Jmp(new_block);
 216         set_Block_cfgpred(block, pos, new_jmp);
 217 }
 218
 219 typedef struct jumpthreading_env_t {
 220         ir_node       *true_block;
 221         ir_node       *cmp;        /**< The Compare node that might be partial evaluated */
 222         ir_relation    relation;   /**< The Compare mode of the Compare node. */
 223         ir_node       *cnst;
 224         ir_tarval     *tv;
 225         ir_visited_t   visited_nr;
 226
 227         ir_node       *cnst_pred;   /**< the block before the constant */
 228         int            cnst_pos;    /**< the pos to the constant block (needed to
 229                                           kill that edge later) */
 230 } jumpthreading_env_t;
 231
 232 static ir_node *copy_and_fix_node(const jumpthreading_env_t *env,
 233                                   ir_node *block, ir_node *copy_block, int j,
 234                                   ir_node *node)
 235 {
 236         int      i, arity;
 237         ir_node *copy;
 238
 239         /* we can evaluate Phis right now, all other nodes get copied */
 240         if (is_Phi(node)) {
 241                 copy = get_Phi_pred(node, j);
 242                 /* we might have to evaluate a Phi-cascade */
 243                 if (get_irn_visited(copy) >= env->visited_nr) {
 244                         copy = (ir_node*)get_irn_link(copy);
 245                 }
 246         } else {
 247                 copy = exact_copy(node);
 248                 set_nodes_block(copy, copy_block);
 249
 250                 assert(get_irn_mode(copy) != mode_X);
 251
 252                 arity = get_irn_arity(copy);
 253                 for (i = 0; i < arity; ++i) {
 254                         ir_node *pred     = get_irn_n(copy, i);
 255                         ir_node *new_pred;
 256
 257                         if (get_nodes_block(pred) != block)
 258                                 continue;
 259
 260                         if (get_irn_visited(pred) >= env->visited_nr) {
 261                                 new_pred = (ir_node*)get_irn_link(pred);
 262                         } else {
 263                                 new_pred = copy_and_fix_node(env, block, copy_block, j, pred);
 264                         }
 265                         DB((dbg, LEVEL_2, ">> Set Pred of %+F to %+F\n", copy, new_pred));
 266                         set_irn_n(copy, i, new_pred);
 267                 }
 268         }
 269
 270         set_irn_link(node, copy);
 271         set_irn_visited(node, env->visited_nr);
 272
 273         return copy;
 274 }
 275
 276 static void copy_and_fix(const jumpthreading_env_t *env, ir_node *block,
 277                          ir_node *copy_block, int j)
 278 {
 279         /* Look at all nodes in the cond_block and copy them into pred */
 280         foreach_out_edge(block, edge) {
 281                 ir_node *node = get_edge_src_irn(edge);
 282                 ir_node *copy;
 283                 ir_mode *mode;
 284
 285                 if (is_End(node)) {
 286                         /* edge is a Keep edge. If the end block is unreachable via normal
 287                          * control flow, we must maintain end's reachability with Keeps.
 288                          */
 289                         keep_alive(copy_block);
 290                         continue;
 291                 }
 292                 /* ignore control flow */
 293                 mode = get_irn_mode(node);
 294                 if (mode == mode_X || is_Cond(node) || is_Switch(node))
 295                         continue;
 296 #ifdef AVOID_PHIB
 297                 /* we may not copy mode_b nodes, because this could produce Phi with
 298                  * mode_bs which can't be handled in all backends. Instead we duplicate
 299                  * the node and move it to its users */
 300                 if (mode == mode_b) {
 301                         ir_node *pred;
 302                         int      pn;
 303
 304                         assert(is_Proj(node));
 305
 306                         pred = get_Proj_pred(node);
 307                         pn   = get_Proj_proj(node);
 308
 309                         foreach_out_edge_safe(node, edge) {
 310                                 ir_node *cmp_copy;
 311                                 ir_node *user       = get_edge_src_irn(edge);
 312                                 int pos             = get_edge_src_pos(edge);
 313                                 ir_node *user_block = get_nodes_block(user);
 314
 315                                 if (user_block == block)
 316                                         continue;
 317
 318                                 cmp_copy = exact_copy(pred);
 319                                 set_nodes_block(cmp_copy, user_block);
 320                                 copy = new_r_Proj(cmp_copy, mode_b, pn);
 321                                 set_irn_n(user, pos, copy);
 322                         }
 323                         continue;
 324                 }
 325 #endif
 326
 327                 copy = copy_and_fix_node(env, block, copy_block, j, node);
 328
 329                 /* we might hit values in blocks that have already been processed by a
 330                  * recursive find_phi_with_const() call */
 331                 assert(get_irn_visited(copy) <= env->visited_nr);
 332                 if (get_irn_visited(copy) >= env->visited_nr) {
 333                         ir_node *prev_copy = (ir_node*)get_irn_link(copy);
 334                         if (prev_copy != NULL)
 335                                 set_irn_link(node, prev_copy);
 336                 }
 337         }
 338
 339         /* fix data-flow (and reconstruct SSA if needed) */
 340         foreach_out_edge(block, edge) {
 341                 ir_node *node = get_edge_src_irn(edge);
 342                 ir_node *copy_node;
 343                 ir_mode *mode;
 344
 345                 mode = get_irn_mode(node);
 346                 if (mode == mode_X || is_Cond(node) || is_Switch(node))
 347                         continue;
 348 #ifdef AVOID_PHIB
 349                 if (mode == mode_b)
 350                         continue;
 351 #endif
 352
 353                 DB((dbg, LEVEL_2, ">> Fixing users of %+F\n", node));
 354
 355                 copy_node = (ir_node*)get_irn_link(node);
 356                 construct_ssa(block, node, copy_block, copy_node);
 357         }
 358
 359         /* make sure new nodes are kept alive if old nodes were */
 360         ir_graph *irg = get_irn_irg(block);
 361         ir_node  *end = get_irg_end(irg);
 362         for (int i = 0, arity = get_End_n_keepalives(end); i < arity; ++i) {
 363                 ir_node *keep = get_End_keepalive(end, i);
 364                 if (get_irn_visited(keep) < env->visited_nr || is_Block(keep))
 365                         continue;
 366                 ir_node *copy = get_irn_link(keep);
 367                 add_End_keepalive(end, copy);
 368         }
 369 }
 370
 371 /**
 372  * returns whether the cmp evaluates to true or false, or can't be evaluated!
 373  * 1: true, 0: false, -1: can't evaluate
 374  *
 375  * @param relation  the compare mode of the Compare
 376  * @param tv_left   the left tarval
 377  * @param tv_right  the right tarval
 378  */
 379 static int eval_cmp_tv(ir_relation relation, ir_tarval *tv_left,
 380                        ir_tarval *tv_right)
 381 {
 382         ir_relation cmp_result = tarval_cmp(tv_left, tv_right);
 383
 384         /* does the compare evaluate to true? */
 385         if (cmp_result == ir_relation_false)
 386                 return -1;
 387         if ((cmp_result & relation) != 0)
 388                 return 1;
 389
 390         return 0;
 391 }
 392
 393 #if 0
 394 /* Matze: disabled, check first if the compare still is correct */
 395
 396 /**
 397  * returns whether the cmp evaluates to true or false according to vrp
 398  * information , or can't be evaluated!
 399  * 1: true, 0: false, -1: can't evaluate
 400  *
 401  * @param relation  the compare mode of the Compare
 402  * @param left      the left node
 403  * @param right     the right node
 404  */
 405 static int eval_cmp_vrp(ir_relation relation, ir_node *left, ir_node *right)
 406 {
 407         ir_relation cmp_result = vrp_cmp(left, right);
 408         /* does the compare evaluate to true? */
 409         if (cmp_result == ir_relation_false)
 410                 return -1;
 411
 412         if ((cmp_result & relation) != cmp_result) {
 413                 if ((cmp_result & relation) != 0) {
 414                         return -1;
 415                 }
 416                 return 0;
 417         }
 418         return 1;
 419 }
 420 #endif
 421
 422 /**
 423  * returns whether the cmp evaluates to true or false, or can't be evaluated!
 424  * 1: true, 0: false, -1: can't evaluate
 425  *
 426  * @param env      the environment
 427  * @param cand     the candidate node, either a Const or a Confirm
 428  */
 429 static int eval_cmp(jumpthreading_env_t *env, ir_node *cand)
 430 {
 431         if (is_Const(cand)) {
 432                 ir_tarval *tv_cand = get_Const_tarval(cand);
 433                 ir_tarval *tv_cmp  = get_Const_tarval(env->cnst);
 434
 435                 return eval_cmp_tv(env->relation, tv_cand, tv_cmp);
 436         } else { /* a Confirm */
 437                 ir_tarval *res = computed_value_Cmp_Confirm(env->cmp, cand, env->cnst, env->relation);
 438
 439                 if (res == tarval_bad)
 440                         return -1;
 441                 return res == tarval_b_true;
 442         }
 443 }
 444
 445 /**
 446  * Check for Const or Confirm with Const.
 447  */
 448 static int is_Const_or_Confirm(const ir_node *node)
 449 {
 450         if (is_Confirm(node))
 451                 node = get_Confirm_bound(node);
 452         return is_Const(node);
 453 }
 454
 455 /**
 456  * get the tarval of a Const or Confirm with
 457  */
 458 static ir_tarval *get_Const_or_Confirm_tarval(const ir_node *node)
 459 {
 460         if (is_Confirm(node)) {
 461                 if (get_Confirm_bound(node))
 462                         node = get_Confirm_bound(node);
 463         }
 464         return get_Const_tarval(node);
 465 }
 466
 467 static ir_node *find_const_or_confirm(jumpthreading_env_t *env, ir_node *jump,
 468                                       ir_node *value)
 469 {
 470         ir_node *block = get_nodes_block(jump);
 471
 472         if (irn_visited_else_mark(value))
 473                 return NULL;
 474
 475         if (is_Const_or_Confirm(value)) {
 476                 if (eval_cmp(env, value) <= 0)
 477                         return NULL;
 478
 479                 DB((
 480                         dbg, LEVEL_1,
 481                         "> Found jump threading candidate %+F->%+F\n",
 482                         block, env->true_block
 483                 ));
 484
 485                 /* adjust true_block to point directly towards our jump */
 486                 add_pred(env->true_block, jump);
 487
 488                 split_critical_edge(env->true_block, 0);
 489
 490                 /* we need a bigger visited nr when going back */
 491                 env->visited_nr++;
 492
 493                 return block;
 494         }
 495
 496         if (is_Phi(value)) {
 497                 int i, arity;
 498
 499                 /* the Phi has to be in the same Block as the Jmp */
 500                 if (get_nodes_block(value) != block)
 501                         return NULL;
 502
 503                 arity = get_irn_arity(value);
 504                 for (i = 0; i < arity; ++i) {
 505                         ir_node *copy_block;
 506                         ir_node *phi_pred = get_Phi_pred(value, i);
 507                         ir_node *cfgpred  = get_Block_cfgpred(block, i);
 508
 509                         copy_block = find_const_or_confirm(env, cfgpred, phi_pred);
 510                         if (copy_block == NULL)
 511                                 continue;
 512
 513                         /* copy duplicated nodes in copy_block and fix SSA */
 514                         copy_and_fix(env, block, copy_block, i);
 515
 516                         if (copy_block == get_nodes_block(cfgpred)) {
 517                                 env->cnst_pred = block;
 518                                 env->cnst_pos  = i;
 519                         }
 520
 521                         /* return now as we can't process more possibilities in 1 run */
 522                         return copy_block;
 523                 }
 524         }
 525
 526         return NULL;
 527 }
 528
 529 static ir_node *find_candidate(jumpthreading_env_t *env, ir_node *jump,
 530                                ir_node *value)
 531 {
 532         ir_node *block = get_nodes_block(jump);
 533
 534         if (irn_visited_else_mark(value)) {
 535                 return NULL;
 536         }
 537
 538         if (is_Const_or_Confirm(value)) {
 539                 ir_tarval *tv = get_Const_or_Confirm_tarval(value);
 540
 541                 if (tv != env->tv)
 542                         return NULL;
 543
 544                 DB((
 545                         dbg, LEVEL_1,
 546                         "> Found jump threading candidate %+F->%+F\n",
 547                         block, env->true_block
 548                 ));
 549
 550                 /* adjust true_block to point directly towards our jump */
 551                 add_pred(env->true_block, jump);
 552
 553                 split_critical_edge(env->true_block, 0);
 554
 555                 /* we need a bigger visited nr when going back */
 556                 env->visited_nr++;
 557
 558                 return block;
 559         }
 560         if (is_Phi(value)) {
 561                 int i, arity;
 562
 563                 /* the Phi has to be in the same Block as the Jmp */
 564                 if (get_nodes_block(value) != block)
 565                         return NULL;
 566
 567                 arity = get_irn_arity(value);
 568                 for (i = 0; i < arity; ++i) {
 569                         ir_node *copy_block;
 570                         ir_node *phi_pred = get_Phi_pred(value, i);
 571                         ir_node *cfgpred  = get_Block_cfgpred(block, i);
 572
 573                         copy_block = find_candidate(env, cfgpred, phi_pred);
 574                         if (copy_block == NULL)
 575                                 continue;
 576
 577                         /* copy duplicated nodes in copy_block and fix SSA */
 578                         copy_and_fix(env, block, copy_block, i);
 579
 580                         if (copy_block == get_nodes_block(cfgpred)) {
 581                                 env->cnst_pred = block;
 582                                 env->cnst_pos  = i;
 583                         }
 584
 585                         /* return now as we can't process more possibilities in 1 run */
 586                         return copy_block;
 587                 }
 588         }
 589         if (is_Cmp(value)) {
 590                 ir_node    *cmp      = value;
 591                 ir_node    *left     = get_Cmp_left(cmp);
 592                 ir_node    *right    = get_Cmp_right(cmp);
 593                 ir_relation relation = get_Cmp_relation(cmp);
 594
 595                 /* we assume that the constant is on the right side, swap left/right
 596                  * if needed */
 597                 if (is_Const(left)) {
 598                         ir_node *t = left;
 599                         left       = right;
 600                         right      = t;
 601
 602                         relation   = get_inversed_relation(relation);
 603                 }
 604
 605                 if (!is_Const(right))
 606                         return NULL;
 607
 608                 if (get_nodes_block(left) != block)
 609                         return NULL;
 610
 611                 /* negate condition when we're looking for the false block */
 612                 if (env->tv == tarval_b_false) {
 613                         relation = get_negated_relation(relation);
 614                 }
 615
 616                 /* (recursively) look if a pred of a Phi is a constant or a Confirm */
 617                 env->cmp      = cmp;
 618                 env->relation = relation;
 619                 env->cnst     = right;
 620
 621                 return find_const_or_confirm(env, jump, left);
 622         }
 623
 624         return NULL;
 625 }
 626
 627 /**
 628  * Block-walker: searches for the following construct
 629  *
 630  *  Const or Phi with constants
 631  *           |
 632  *          Cmp
 633  *           |
 634  *         Cond
 635  *          /
 636  *       ProjX
 637  *        /
 638  *     Block
 639  */
 640 static void thread_jumps(ir_node* block, void* data)
 641 {
 642         jumpthreading_env_t env;
 643         bool *changed = (bool*)data;
 644         ir_node *selector;
 645         ir_node *projx;
 646         ir_node *cond;
 647         ir_node *copy_block;
 648         int      selector_evaluated;
 649         ir_graph *irg;
 650         ir_node *badX;
 651         int      cnst_pos;
 652
 653         /* we do not deal with Phis, so restrict this to exactly one cfgpred */
 654         if (get_Block_n_cfgpreds(block) != 1)
 655                 return;
 656
 657         projx = get_Block_cfgpred(block, 0);
 658         if (!is_Proj(projx))
 659                 return;
 660         assert(get_irn_mode(projx) == mode_X);
 661
 662         cond = get_Proj_pred(projx);
 663         /* TODO handle switch Conds */
 664         if (!is_Cond(cond))
 665                 return;
 666
 667         /* handle cases that can be immediately evaluated */
 668         selector = get_Cond_selector(cond);
 669         selector_evaluated = -1;
 670         if (is_Cmp(selector)) {
 671                 ir_node *left  = get_Cmp_left(selector);
 672                 ir_node *right = get_Cmp_right(selector);
 673                 if (is_Const(left) && is_Const(right)) {
 674                         ir_relation relation = get_Cmp_relation(selector);
 675                         ir_tarval  *tv_left  = get_Const_tarval(left);
 676                         ir_tarval  *tv_right = get_Const_tarval(right);
 677
 678                         selector_evaluated = eval_cmp_tv(relation, tv_left, tv_right);
 679                 }
 680 #if 0
 681                 if (selector_evaluated < 0) {
 682                         /* This is only the case if the predecessor nodes are not
 683                          * constant or the comparison could not be evaluated.
 684                          * Try with VRP information now.
 685                          */
 686                         selector_evaluated = eval_cmp_vrp(relation, left, right);
 687                 }
 688 #endif
 689         } else if (is_Const_or_Confirm(selector)) {
 690                 ir_tarval *tv = get_Const_or_Confirm_tarval(selector);
 691                 if (tv == tarval_b_true) {
 692                         selector_evaluated = 1;
 693                 } else {
 694                         assert(tv == tarval_b_false);
 695                         selector_evaluated = 0;
 696                 }
 697         }
 698
 699         env.cnst_pred = NULL;
 700         if (get_Proj_proj(projx) == pn_Cond_false) {
 701                 env.tv = tarval_b_false;
 702                 if (selector_evaluated >= 0)
 703                         selector_evaluated = !selector_evaluated;
 704         } else {
 705                 env.tv = tarval_b_true;
 706         }
 707
 708         if (selector_evaluated == 0) {
 709                 ir_graph *irg = get_irn_irg(block);
 710                 ir_node  *bad = new_r_Bad(irg, mode_X);
 711                 exchange(projx, bad);
 712                 *changed = true;
 713                 return;
 714         } else if (selector_evaluated == 1) {
 715                 dbg_info *dbgi = get_irn_dbg_info(selector);
 716                 ir_node  *jmp  = new_rd_Jmp(dbgi, get_nodes_block(projx));
 717                 DBG_OPT_JUMPTHREADING(projx, jmp);
 718                 exchange(projx, jmp);
 719                 *changed = true;
 720                 return;
 721         }
 722
 723         /* (recursively) look if a pred of a Phi is a constant or a Confirm */
 724         env.true_block = block;
 725         irg = get_irn_irg(block);
 726         inc_irg_visited(irg);
 727         env.visited_nr = get_irg_visited(irg);
 728
 729         copy_block = find_candidate(&env, projx, selector);
 730         if (copy_block == NULL)
 731                 return;
 732
 733         /* We might thread the condition block of an infinite loop,
 734          * such that there is no path to End anymore. */
 735         keep_alive(block);
 736
 737         /* we have to remove the edge towards the pred as the pred now
 738          * jumps into the true_block. We also have to shorten Phis
 739          * in our block because of this */
 740         badX     = new_r_Bad(irg, mode_X);
 741         cnst_pos = env.cnst_pos;
 742
 743         /* shorten Phis */
 744         foreach_out_edge_safe(env.cnst_pred, edge) {
 745                 ir_node *node = get_edge_src_irn(edge);
 746
 747                 if (is_Phi(node)) {
 748                         ir_node *bad = new_r_Bad(irg, get_irn_mode(node));
 749                         set_Phi_pred(node, cnst_pos, bad);
 750                 }
 751         }
 752
 753         set_Block_cfgpred(env.cnst_pred, cnst_pos, badX);
 754
 755         /* the graph is changed now */
 756         *changed = true;
 757 }
 758
 759 void opt_jumpthreading(ir_graph* irg)
 760 {
 761         bool changed;
 762         bool rerun;
 763
 764         assure_irg_properties(irg,
 765                 IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE
 766                 | IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES
 767                 | IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES);
 768
 769         FIRM_DBG_REGISTER(dbg, "firm.opt.jumpthreading");
 770
 771         DB((dbg, LEVEL_1, "===> Performing jumpthreading on %+F\n", irg));
 772
 773         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_IRN_VISITED);
 774
 775         changed = false;
 776         do {
 777                 rerun = false;
 778                 irg_block_walk_graph(irg, thread_jumps, NULL, &rerun);
 779                 changed |= rerun;
 780         } while (rerun);
 781
 782         ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_IRN_VISITED);
 783
 784         confirm_irg_properties(irg,
 785                 changed ? IR_GRAPH_PROPERTIES_NONE : IR_GRAPH_PROPERTIES_ALL);
 786 }
 787
 788 /* Creates an ir_graph pass for opt_jumpthreading. */
 789 ir_graph_pass_t *opt_jumpthreading_pass(const char *name)
 790 {
 791         return def_graph_pass(name ? name : "jumpthreading", opt_jumpthreading);
 792 }