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         ir_node *next;
  61         ir_entity *block_entity;
  62         const int max = get_irn_arity(block);
  63         const int new_max = count_non_bads(block);
  64         assert(max >= new_max);
  65
  66         if (is_Bad(block) || max == new_max)
  67                 return;
  68
  69         new_in = ALLOCAN(ir_node*, new_max);
  70         *changed = 1;
  71
  72         assert(get_Block_dom_depth(block) >= 0);
  73
  74         /* 1. Create a new block without Bad inputs */
  75         for (i = j = 0; i < max; ++i) {
  76                 ir_node *block_pred = get_irn_n(block, i);
  77                 if (!is_Bad(block_pred)) {
  78                         new_in[j++] = block_pred;
  79                 }
  80         }
  81         assert(j == new_max);
  82
  83         /* If the end block is unreachable, it might have zero predecessors. */
  84         if (new_max == 0) {
  85                 ir_node *end_block = get_irg_end_block(get_irn_irg(block));
  86                 if (block == end_block) {
  87                         set_irn_in(block, new_max, new_in);
  88                         return;
  89                 }
  90         }
  91
  92         new_block = new_r_Block(get_irn_irg(block), new_max, new_in);
  93         block_entity = get_Block_entity(block);
  94         if (block_entity)
  95                 set_Block_entity(new_block, block_entity);
  96
  97         /* 2. Remove inputs on Phis, where the block input is Bad. */
  98         for (phi = get_Block_phis(block); phi != NULL; phi = next) {
  99                 ir_node *new_phi;
 100
 101                 next = get_Phi_next(phi);
 102                 assert(get_irn_arity(phi) == max);
 103
 104                 for (i = j = 0; i < max; ++i) {
 105                         ir_node *block_pred = get_irn_n(block, i);
 106
 107                         if (!is_Bad(block_pred)) {
 108                                 ir_node *pred = get_irn_n(phi, i);
 109                                 new_in[j++] = pred;
 110                         }
 111                 }
 112                 assert(j == new_max);
 113
 114                 new_phi = new_r_Phi(new_block, new_max, new_in, get_irn_mode(phi));
 115                 exchange(phi, new_phi);
 116         }
 117
 118         exchange(block, new_block);
 119 }
 120
 121 /* Remove Bad nodes from Phi and Block inputs.
 122  *
 123  * This does NOT remove unreachable code.
 124  *
 125  * Postcondition: No Bad nodes.
 126  */
 127 int remove_bads(ir_graph *irg)
 128 {
 129         int changed = 0;
 130         /* build phi list per block */
 131         irg_walk_graph(irg, firm_clear_block_phis, firm_collect_block_phis, NULL);
 132
 133         /* actually remove Bads */
 134         irg_block_walk_graph(irg, NULL, block_remove_bads, (void *)&changed);
 135
 136         if (changed) {
 137                 edges_deactivate(irg);
 138                 clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_OUTS);
 139                 clear_irg_state(irg, IR_GRAPH_STATE_CONSISTENT_DOMINANCE);
 140         }
 141
 142         return changed;
 143 }