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  * @version $Id$
  26  */
  27 #include "config.h"
  28
  29 #include "iroptimize.h"
  30
  31 #include <assert.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 "opt_manage.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         const ir_edge_t *edge;
 154         const ir_edge_t *next;
 155
 156         /* no need to do anything */
 157         if (orig_val == second_val)
 158                 return;
 159
 160         irg = get_irn_irg(orig_val);
 161         inc_irg_visited(irg);
 162
 163         mode = get_irn_mode(orig_val);
 164         set_irn_link(orig_block, orig_val);
 165         mark_irn_visited(orig_block);
 166
 167         ssa_second_def_block = second_block;
 168         ssa_second_def       = second_val;
 169
 170         /* Only fix the users of the first, i.e. the original node */
 171         foreach_out_edge_safe(orig_val, edge, next) {
 172                 ir_node *user = get_edge_src_irn(edge);
 173                 int j = get_edge_src_pos(edge);
 174                 ir_node *user_block = get_nodes_block(user);
 175                 ir_node *newval;
 176
 177                 /* ignore keeps */
 178                 if (is_End(user))
 179                         continue;
 180
 181                 DB((dbg, LEVEL_3, ">>> Fixing user %+F (pred %d == %+F)\n", user, j, get_irn_n(user, j)));
 182
 183                 if (is_Phi(user)) {
 184                         ir_node *pred_block = get_Block_cfgpred_block(user_block, j);
 185                         newval = search_def_and_create_phis(pred_block, mode, 1);
 186                 } else {
 187                         newval = search_def_and_create_phis(user_block, mode, 1);
 188                 }
 189
 190                 /* don't fix newly created Phis from the SSA construction */
 191                 if (newval != user) {
 192                         DB((dbg, LEVEL_4, ">>>> Setting input %d of %+F to %+F\n", j, user, newval));
 193                         set_irn_n(user, j, newval);
 194                 }
 195         }
 196 }
 197
 198 /**
 199  * jumpthreading produces critical edges, e.g. B-C:
 200  *     A         A
 201  *  \ /       \  |
 202  *   B    =>   B |
 203  *  / \       / \|
 204  *     C         C
 205  *
 206  * By splitting this critical edge more threadings might be possible.
 207  */
 208 static void split_critical_edge(ir_node *block, int pos)
 209 {
 210         ir_graph *irg = get_irn_irg(block);
 211         ir_node *in[1];
 212         ir_node *new_block;
 213         ir_node *new_jmp;
 214
 215         in[0] = get_Block_cfgpred(block, pos);
 216         new_block = new_r_Block(irg, 1, in);
 217         new_jmp = new_r_Jmp(new_block);
 218         set_Block_cfgpred(block, pos, new_jmp);
 219 }
 220
 221 typedef struct jumpthreading_env_t {
 222         ir_node       *true_block;
 223         ir_node       *cmp;        /**< The Compare node that might be partial evaluated */
 224         ir_relation    relation;   /**< The Compare mode of the Compare node. */
 225         ir_node       *cnst;
 226         ir_tarval     *tv;
 227         ir_visited_t   visited_nr;
 228
 229         ir_node       *cnst_pred;   /**< the block before the constant */
 230         int            cnst_pos;    /**< the pos to the constant block (needed to
 231                                           kill that edge later) */
 232 } jumpthreading_env_t;
 233
 234 static ir_node *copy_and_fix_node(const jumpthreading_env_t *env,
 235                                   ir_node *block, ir_node *copy_block, int j,
 236                                   ir_node *node)
 237 {
 238         int      i, arity;
 239         ir_node *copy;
 240
 241         /* we can evaluate Phis right now, all other nodes get copied */
 242         if (is_Phi(node)) {
 243                 copy = get_Phi_pred(node, j);
 244                 /* we might have to evaluate a Phi-cascade */
 245                 if (get_irn_visited(copy) >= env->visited_nr) {
 246                         copy = (ir_node*)get_irn_link(copy);
 247                 }
 248         } else {
 249                 copy = exact_copy(node);
 250                 set_nodes_block(copy, copy_block);
 251
 252                 assert(get_irn_mode(copy) != mode_X);
 253
 254                 arity = get_irn_arity(copy);
 255                 for (i = 0; i < arity; ++i) {
 256                         ir_node *pred     = get_irn_n(copy, i);
 257                         ir_node *new_pred;
 258
 259                         if (get_nodes_block(pred) != block)
 260                                 continue;
 261
 262                         if (get_irn_visited(pred) >= env->visited_nr) {
 263                                 new_pred = (ir_node*)get_irn_link(pred);
 264                         } else {
 265                                 new_pred = copy_and_fix_node(env, block, copy_block, j, pred);
 266                         }
 267                         DB((dbg, LEVEL_2, ">> Set Pred of %+F to %+F\n", copy, new_pred));
 268                         set_irn_n(copy, i, new_pred);
 269                 }
 270         }
 271
 272         set_irn_link(node, copy);
 273         set_irn_visited(node, env->visited_nr);
 274
 275         return copy;
 276 }
 277
 278 static void copy_and_fix(const jumpthreading_env_t *env, ir_node *block,
 279                          ir_node *copy_block, int j)
 280 {
 281         const ir_edge_t *edge;
 282
 283         /* Look at all nodes in the cond_block and copy them into pred */
 284         foreach_out_edge(block, edge) {
 285                 ir_node *node = get_edge_src_irn(edge);
 286                 ir_node *copy;
 287                 ir_mode *mode;
 288
 289                 if (is_End(node)) {
 290                         /* edge is a Keep edge. If the end block is unreachable via normal control flow,
 291                          * we must maintain end's reachability with Keeps.
 292                          */
 293                         keep_alive(copy_block);
 294                         continue;
 295                 }
 296                 /* ignore control flow */
 297                 mode = get_irn_mode(node);
 298                 if (mode == mode_X || is_Cond(node))
 299                         continue;
 300 #ifdef AVOID_PHIB
 301                 /* we may not copy mode_b nodes, because this could produce Phi with
 302                  * mode_bs which can't be handled in all backends. Instead we duplicate
 303                  * the node and move it to its users */
 304                 if (mode == mode_b) {
 305                         const ir_edge_t *edge, *next;
 306                         ir_node *pred;
 307                         int      pn;
 308
 309                         assert(is_Proj(node));
 310
 311                         pred = get_Proj_pred(node);
 312                         pn   = get_Proj_proj(node);
 313
 314                         foreach_out_edge_safe(node, edge, next) {
 315                                 ir_node *cmp_copy;
 316                                 ir_node *user       = get_edge_src_irn(edge);
 317                                 int pos             = get_edge_src_pos(edge);
 318                                 ir_node *user_block = get_nodes_block(user);
 319
 320                                 if (user_block == block)
 321                                         continue;
 322
 323                                 cmp_copy = exact_copy(pred);
 324                                 set_nodes_block(cmp_copy, user_block);
 325                                 copy = new_r_Proj(cmp_copy, mode_b, pn);
 326                                 set_irn_n(user, pos, copy);
 327                         }
 328                         continue;
 329                 }
 330 #endif
 331
 332                 copy = copy_and_fix_node(env, block, copy_block, j, node);
 333
 334                 /* we might hit values in blocks that have already been processed by a
 335                  * recursive find_phi_with_const() call */
 336                 assert(get_irn_visited(copy) <= env->visited_nr);
 337                 if (get_irn_visited(copy) >= env->visited_nr) {
 338                         ir_node *prev_copy = (ir_node*)get_irn_link(copy);
 339                         if (prev_copy != NULL)
 340                                 set_irn_link(node, prev_copy);
 341                 }
 342         }
 343
 344         /* fix data-flow (and reconstruct SSA if needed) */
 345         foreach_out_edge(block, edge) {
 346                 ir_node *node = get_edge_src_irn(edge);
 347                 ir_node *copy_node;
 348                 ir_mode *mode;
 349
 350                 mode = get_irn_mode(node);
 351                 if (mode == mode_X || is_Cond(node))
 352                         continue;
 353 #ifdef AVOID_PHIB
 354                 if (mode == mode_b)
 355                         continue;
 356 #endif
 357
 358                 DB((dbg, LEVEL_2, ">> Fixing users of %+F\n", node));
 359
 360                 copy_node = (ir_node*)get_irn_link(node);
 361                 construct_ssa(block, node, copy_block, copy_node);
 362         }
 363 }
 364
 365 /**
 366  * returns whether the cmp evaluates to true or false, or can't be evaluated!
 367  * 1: true, 0: false, -1: can't evaluate
 368  *
 369  * @param relation  the compare mode of the Compare
 370  * @param tv_left   the left tarval
 371  * @param tv_right  the right tarval
 372  */
 373 static int eval_cmp_tv(ir_relation relation, ir_tarval *tv_left,
 374                        ir_tarval *tv_right)
 375 {
 376         ir_relation cmp_result = tarval_cmp(tv_left, tv_right);
 377
 378         /* does the compare evaluate to true? */
 379         if (cmp_result == ir_relation_false)
 380                 return -1;
 381         if ((cmp_result & relation) != 0)
 382                 return 1;
 383
 384         return 0;
 385 }
 386
 387 #if 0
 388 /* Matze: disabled, check first if the compare still is correct */
 389
 390 /**
 391  * returns whether the cmp evaluates to true or false according to vrp
 392  * information , or can't be evaluated!
 393  * 1: true, 0: false, -1: can't evaluate
 394  *
 395  * @param relation  the compare mode of the Compare
 396  * @param left      the left node
 397  * @param right     the right node
 398  */
 399 static int eval_cmp_vrp(ir_relation relation, ir_node *left, ir_node *right)
 400 {
 401         ir_relation cmp_result = vrp_cmp(left, right);
 402         /* does the compare evaluate to true? */
 403         if (cmp_result == ir_relation_false)
 404                 return -1;
 405
 406         if ((cmp_result & relation) != cmp_result) {
 407                 if ((cmp_result & relation) != 0) {
 408                         return -1;
 409                 }
 410                 return 0;
 411         }
 412         return 1;
 413 }
 414 #endif
 415
 416 /**
 417  * returns whether the cmp evaluates to true or false, or can't be evaluated!
 418  * 1: true, 0: false, -1: can't evaluate
 419  *
 420  * @param env      the environment
 421  * @param cand     the candidate node, either a Const or a Confirm
 422  */
 423 static int eval_cmp(jumpthreading_env_t *env, ir_node *cand)
 424 {
 425         if (is_Const(cand)) {
 426                 ir_tarval *tv_cand = get_Const_tarval(cand);
 427                 ir_tarval *tv_cmp  = get_Const_tarval(env->cnst);
 428
 429                 return eval_cmp_tv(env->relation, tv_cand, tv_cmp);
 430         } else { /* a Confirm */
 431                 ir_tarval *res = computed_value_Cmp_Confirm(env->cmp, cand, env->cnst, env->relation);
 432
 433                 if (res == tarval_bad)
 434                         return -1;
 435                 return res == tarval_b_true;
 436         }
 437 }
 438
 439 /**
 440  * Check for Const or Confirm with Const.
 441  */
 442 static int is_Const_or_Confirm(const ir_node *node)
 443 {
 444         if (is_Confirm(node))
 445                 node = get_Confirm_bound(node);
 446         return is_Const(node);
 447 }
 448
 449 /**
 450  * get the tarval of a Const or Confirm with
 451  */
 452 static ir_tarval *get_Const_or_Confirm_tarval(const ir_node *node)
 453 {
 454         if (is_Confirm(node)) {
 455                 if (get_Confirm_bound(node))
 456                         node = get_Confirm_bound(node);
 457         }
 458         return get_Const_tarval(node);
 459 }
 460
 461 static ir_node *find_const_or_confirm(jumpthreading_env_t *env, ir_node *jump,
 462                                       ir_node *value)
 463 {
 464         ir_node *block = get_nodes_block(jump);
 465
 466         if (irn_visited_else_mark(value))
 467                 return NULL;
 468
 469         if (is_Const_or_Confirm(value)) {
 470                 if (eval_cmp(env, value) <= 0)
 471                         return NULL;
 472
 473                 DB((
 474                         dbg, LEVEL_1,
 475                         "> Found jump threading candidate %+F->%+F\n",
 476                         env->true_block, block
 477                 ));
 478
 479                 /* adjust true_block to point directly towards our jump */
 480                 add_pred(env->true_block, jump);
 481
 482                 split_critical_edge(env->true_block, 0);
 483
 484                 /* we need a bigger visited nr when going back */
 485                 env->visited_nr++;
 486
 487                 return block;
 488         }
 489
 490         if (is_Phi(value)) {
 491                 int i, arity;
 492
 493                 /* the Phi has to be in the same Block as the Jmp */
 494                 if (get_nodes_block(value) != block)
 495                         return NULL;
 496
 497                 arity = get_irn_arity(value);
 498                 for (i = 0; i < arity; ++i) {
 499                         ir_node *copy_block;
 500                         ir_node *phi_pred = get_Phi_pred(value, i);
 501                         ir_node *cfgpred  = get_Block_cfgpred(block, i);
 502
 503                         copy_block = find_const_or_confirm(env, cfgpred, phi_pred);
 504                         if (copy_block == NULL)
 505                                 continue;
 506
 507                         /* copy duplicated nodes in copy_block and fix SSA */
 508                         copy_and_fix(env, block, copy_block, i);
 509
 510                         if (copy_block == get_nodes_block(cfgpred)) {
 511                                 env->cnst_pred = block;
 512                                 env->cnst_pos  = i;
 513                         }
 514
 515                         /* return now as we can't process more possibilities in 1 run */
 516                         return copy_block;
 517                 }
 518         }
 519
 520         return NULL;
 521 }
 522
 523 static ir_node *find_candidate(jumpthreading_env_t *env, ir_node *jump,
 524                                ir_node *value)
 525 {
 526         ir_node *block = get_nodes_block(jump);
 527
 528         if (irn_visited_else_mark(value)) {
 529                 return NULL;
 530         }
 531
 532         if (is_Const_or_Confirm(value)) {
 533                 ir_tarval *tv = get_Const_or_Confirm_tarval(value);
 534
 535                 if (tv != env->tv)
 536                         return NULL;
 537
 538                 DB((
 539                         dbg, LEVEL_1,
 540                         "> Found jump threading candidate %+F->%+F\n",
 541                         env->true_block, block
 542                 ));
 543
 544                 /* adjust true_block to point directly towards our jump */
 545                 add_pred(env->true_block, jump);
 546
 547                 split_critical_edge(env->true_block, 0);
 548
 549                 /* we need a bigger visited nr when going back */
 550                 env->visited_nr++;
 551
 552                 return block;
 553         }
 554         if (is_Phi(value)) {
 555                 int i, arity;
 556
 557                 /* the Phi has to be in the same Block as the Jmp */
 558                 if (get_nodes_block(value) != block)
 559                         return NULL;
 560
 561                 arity = get_irn_arity(value);
 562                 for (i = 0; i < arity; ++i) {
 563                         ir_node *copy_block;
 564                         ir_node *phi_pred = get_Phi_pred(value, i);
 565                         ir_node *cfgpred  = get_Block_cfgpred(block, i);
 566
 567                         copy_block = find_candidate(env, cfgpred, phi_pred);
 568                         if (copy_block == NULL)
 569                                 continue;
 570
 571                         /* copy duplicated nodes in copy_block and fix SSA */
 572                         copy_and_fix(env, block, copy_block, i);
 573
 574                         if (copy_block == get_nodes_block(cfgpred)) {
 575                                 env->cnst_pred = block;
 576                                 env->cnst_pos  = i;
 577                         }
 578
 579                         /* return now as we can't process more possibilities in 1 run */
 580                         return copy_block;
 581                 }
 582         }
 583         if (is_Cmp(value)) {
 584                 ir_node    *cmp      = value;
 585                 ir_node    *left     = get_Cmp_left(cmp);
 586                 ir_node    *right    = get_Cmp_right(cmp);
 587                 ir_relation relation = get_Cmp_relation(cmp);
 588
 589                 /* we assume that the constant is on the right side, swap left/right
 590                  * if needed */
 591                 if (is_Const(left)) {
 592                         ir_node *t = left;
 593                         left       = right;
 594                         right      = t;
 595
 596                         relation   = get_inversed_relation(relation);
 597                 }
 598
 599                 if (!is_Const(right))
 600                         return NULL;
 601
 602                 if (get_nodes_block(left) != block)
 603                         return NULL;
 604
 605                 /* negate condition when we're looking for the false block */
 606                 if (env->tv == tarval_b_false) {
 607                         relation = get_negated_relation(relation);
 608                 }
 609
 610                 /* (recursively) look if a pred of a Phi is a constant or a Confirm */
 611                 env->cmp      = cmp;
 612                 env->relation = relation;
 613                 env->cnst     = right;
 614
 615                 return find_const_or_confirm(env, jump, left);
 616         }
 617
 618         return NULL;
 619 }
 620
 621 /**
 622  * Block-walker: searches for the following construct
 623  *
 624  *  Const or Phi with constants
 625  *           |
 626  *          Cmp
 627  *           |
 628  *         Cond
 629  *          /
 630  *       ProjX
 631  *        /
 632  *     Block
 633  */
 634 static void thread_jumps(ir_node* block, void* data)
 635 {
 636         jumpthreading_env_t env;
 637         int *changed = (int*)data;
 638         ir_node *selector;
 639         ir_node *projx;
 640         ir_node *cond;
 641         ir_node *copy_block;
 642         int      selector_evaluated;
 643         const ir_edge_t *edge, *next;
 644         ir_graph *irg;
 645         ir_node *badX;
 646         int      cnst_pos;
 647
 648         /* we do not deal with Phis, so restrict this to exactly one cfgpred */
 649         if (get_Block_n_cfgpreds(block) != 1)
 650                 return;
 651
 652         projx = get_Block_cfgpred(block, 0);
 653         if (!is_Proj(projx))
 654                 return;
 655         assert(get_irn_mode(projx) == mode_X);
 656
 657         cond = get_Proj_pred(projx);
 658         if (!is_Cond(cond))
 659                 return;
 660
 661         selector = get_Cond_selector(cond);
 662         /* TODO handle switch Conds */
 663         if (get_irn_mode(selector) != mode_b)
 664                 return;
 665
 666         /* handle cases that can be immediately evaluated */
 667         selector_evaluated = -1;
 668         if (is_Cmp(selector)) {
 669                 ir_node *left  = get_Cmp_left(selector);
 670                 ir_node *right = get_Cmp_right(selector);
 671                 if (is_Const(left) && is_Const(right)) {
 672                         ir_relation relation = get_Cmp_relation(selector);
 673                         ir_tarval  *tv_left  = get_Const_tarval(left);
 674                         ir_tarval  *tv_right = get_Const_tarval(right);
 675
 676                         selector_evaluated = eval_cmp_tv(relation, tv_left, tv_right);
 677                 }
 678 #if 0
 679                 if (selector_evaluated < 0) {
 680                         /* This is only the case if the predecessor nodes are not
 681                          * constant or the comparison could not be evaluated.
 682                          * Try with VRP information now.
 683                          */
 684                         selector_evaluated = eval_cmp_vrp(relation, left, right);
 685                 }
 686 #endif
 687         } else if (is_Const_or_Confirm(selector)) {
 688                 ir_tarval *tv = get_Const_or_Confirm_tarval(selector);
 689                 if (tv == tarval_b_true) {
 690                         selector_evaluated = 1;
 691                 } else {
 692                         assert(tv == tarval_b_false);
 693                         selector_evaluated = 0;
 694                 }
 695         }
 696
 697         env.cnst_pred = NULL;
 698         if (get_Proj_proj(projx) == pn_Cond_false) {
 699                 env.tv = tarval_b_false;
 700                 if (selector_evaluated >= 0)
 701                         selector_evaluated = !selector_evaluated;
 702         } else {
 703                 env.tv = tarval_b_true;
 704         }
 705
 706         if (selector_evaluated == 0) {
 707                 ir_graph *irg = get_irn_irg(block);
 708                 ir_node  *bad = new_r_Bad(irg, mode_X);
 709                 exchange(projx, bad);
 710                 *changed = 1;
 711                 return;
 712         } else if (selector_evaluated == 1) {
 713                 dbg_info *dbgi = get_irn_dbg_info(selector);
 714                 ir_node  *jmp  = new_rd_Jmp(dbgi, get_nodes_block(projx));
 715                 DBG_OPT_JUMPTHREADING(projx, jmp);
 716                 exchange(projx, jmp);
 717                 *changed = 1;
 718                 return;
 719         }
 720
 721         /* (recursively) look if a pred of a Phi is a constant or a Confirm */
 722         env.true_block = block;
 723         irg = get_irn_irg(block);
 724         inc_irg_visited(irg);
 725         env.visited_nr = get_irg_visited(irg);
 726
 727         copy_block = find_candidate(&env, projx, selector);
 728         if (copy_block == NULL)
 729                 return;
 730
 731         /* We might thread the condition block of an infinite loop,
 732          * such that there is no path to End anymore. */
 733         keep_alive(block);
 734
 735         /* we have to remove the edge towards the pred as the pred now
 736          * jumps into the true_block. We also have to shorten Phis
 737          * in our block because of this */
 738         badX     = new_r_Bad(irg, mode_X);
 739         cnst_pos = env.cnst_pos;
 740
 741         /* shorten Phis */
 742         foreach_out_edge_safe(env.cnst_pred, edge, next) {
 743                 ir_node *node = get_edge_src_irn(edge);
 744
 745                 if (is_Phi(node)) {
 746                         ir_node *bad = new_r_Bad(irg, get_irn_mode(node));
 747                         set_Phi_pred(node, cnst_pos, bad);
 748                 }
 749         }
 750
 751         set_Block_cfgpred(env.cnst_pred, cnst_pos, badX);
 752
 753         /* the graph is changed now */
 754         *changed = 1;
 755 }
 756
 757 static ir_graph_state_t do_jumpthread(ir_graph* irg)
 758 {
 759         int changed, rerun;
 760         ir_graph_state_t res = 0;
 761
 762         FIRM_DBG_REGISTER(dbg, "firm.opt.jumpthreading");
 763
 764         DB((dbg, LEVEL_1, "===> Performing jumpthreading on %+F\n", irg));
 765
 766         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_IRN_VISITED);
 767
 768         changed = 0;
 769         do {
 770                 rerun = 0;
 771                 irg_block_walk_graph(irg, thread_jumps, NULL, &rerun);
 772                 changed |= rerun;
 773         } while (rerun);
 774
 775         ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_IRN_VISITED);
 776
 777         if (!changed) {
 778                 res |= IR_GRAPH_STATE_CONSISTENT_DOMINANCE | IR_GRAPH_STATE_CONSISTENT_ENTITY_USAGE;
 779         }
 780
 781         return res;
 782 }
 783
 784 static optdesc_t opt_jumpthread = {
 785         "jumpthreading",
 786         IR_GRAPH_STATE_NO_UNREACHABLE_CODE | IR_GRAPH_STATE_CONSISTENT_OUT_EDGES | IR_GRAPH_STATE_NO_CRITICAL_EDGES,
 787         do_jumpthread,
 788 };
 789
 790 void opt_jumpthreading(ir_graph* irg)
 791 {
 792         perform_irg_optimization(irg, &opt_jumpthread);
 793 }
 794
 795 /* Creates an ir_graph pass for opt_jumpthreading. */
 796 ir_graph_pass_t *opt_jumpthreading_pass(const char *name)
 797 {
 798         return def_graph_pass(name ? name : "jumpthreading", opt_jumpthreading);
 799 }  /* opt_jumpthreading_pass */