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