nsz Git - libfirm/blob - ir/ir/rm_bads.c

   1 /*
   2  * Copyright (C) 1995-2008 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  * @brief    Remove all Bad nodes from ir graph
  22  * @author   Andreas Zwinkau
  23  */
  24 #include "config.h"
  25
  26 #include <assert.h>
  27
  28 #include "irnode_t.h"
  29
  30 #include "irgopt.h"
  31 #include "irgmod.h"
  32 #include "irgwalk.h"
  33
  34 #include "irtools.h"
  35
  36 /**
  37  * Return the number of non-Bad predecessors of the given node.
  38  */
  39 static int count_non_bads(ir_node *node)
  40 {
  41         int arity = get_irn_arity(node);
  42         int count = 0;
  43         int i;
  44         for (i = 0; i < arity; ++i) {
  45                 if (!is_Bad(get_irn_n(node, i)))
  46                         ++count;
  47         }
  48         return count;
  49 }
  50
  51 /**
  52  * Block-walker, remove Bad block predecessors and shorten Phis.
  53  * Phi links must be uptodate.
  54  */
  55 static void block_remove_bads(ir_node *block, void *env)
  56 {
  57         int *changed = (int *)env;
  58         int i, j;
  59         ir_node **new_in, *new_block, *phi;
  60         const int max = get_irn_arity(block);
  61         const int new_max = count_non_bads(block);
  62         assert(max >= new_max);
  63
  64         if (is_Bad(block) || max == new_max)
  65                 return;
  66
  67         new_in = ALLOCAN(ir_node*, new_max);
  68         *changed = 1;
  69
  70         assert(get_Block_dom_depth(block) >= 0);
  71
  72         /* 1. Create a new block without Bad inputs */
  73         for (i = j = 0; i < max; ++i) {
  74                 ir_node *block_pred = get_irn_n(block, i);
  75                 if (!is_Bad(block_pred)) {
  76                         new_in[j++] = block_pred;
  77                 }
  78         }
  79         assert(j == new_max);
  80
  81         /* If the end block is unreachable, it might have zero predecessors. */
  82         if (new_max == 0) {
  83                 ir_node *end_block = get_irg_end_block(get_irn_irg(block));
  84                 if (block == end_block) {
  85                         set_irn_in(block, new_max, new_in);
  86                         return;
  87                 }
  88         }
  89
  90         new_block = new_r_Block(get_irn_irg(block), new_max, new_in);
  91
  92         /* 2. Remove inputs on Phis, where the block input is Bad. */
  93         phi = get_Block_phis(block);
  94         if (phi != NULL) {
  95                 do {
  96                         ir_node *next = get_Phi_next(phi);
  97                         if (get_irn_arity(phi) != new_max) {
  98                                 ir_node *new_phi;
  99
 100                                 for (i = j = 0; i < max; ++i) {
 101                                         ir_node *block_pred = get_irn_n(block, i);
 102
 103                                         if (!is_Bad(block_pred)) {
 104                                                 ir_node *pred = get_irn_n(phi, i);
 105                                                 new_in[j++] = pred;
 106                                         }
 107                                 }
 108                                 assert(j == new_max);
 109
 110                                 new_phi = new_r_Phi(new_block, new_max, new_in, get_irn_mode(phi));
 111                                 exchange(phi, new_phi);
 112                         }
 113                         phi = next;
 114                 } while (phi != NULL);
 115         }
 116
 117         exchange(block, new_block);
 118 }
 119
 120 /* Remove Bad nodes from Phi and Block inputs.
 121  *
 122  * This does NOT remove unreachable code.
 123  *
 124  * Postcondition: No Bad nodes.
 125  */
 126 int remove_bads(ir_graph *irg)
 127 {
 128         int changed = 0;
 129         /* build phi list per block */
 130         irg_walk_graph(irg, firm_clear_block_phis, firm_collect_block_phis, NULL);
 131
 132         /* actually remove Bads */
 133         irg_block_walk_graph(irg, NULL, block_remove_bads, (void *)&changed);
 134
 135         if (changed) {
 136                 edges_deactivate(irg);
 137                 set_irg_outs_inconsistent(irg);
 138         }
 139
 140         return changed;
 141 }