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_Block_n_cfgpreds(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)
  56 {
  57         ir_graph  *irg     = get_irn_irg(block);
  58         const int  max     = get_Block_n_cfgpreds(block);
  59         const int  new_max = count_non_bads(block);
  60         ir_node  **new_in  = ALLOCAN(ir_node*, new_max);
  61         int        i;
  62         int        j;
  63         ir_node   *new_block;
  64         ir_node   *phi;
  65         ir_node   *next;
  66         ir_entity *block_entity;
  67         assert(max >= new_max);
  68
  69         /* 1. Create a new block without Bad inputs */
  70         for (i = j = 0; i < max; ++i) {
  71                 ir_node *const block_pred = get_Block_cfgpred(block, i);
  72                 if (!is_Bad(block_pred)) {
  73                         new_in[j++] = block_pred;
  74                 }
  75         }
  76         assert(j == new_max);
  77
  78         /* If the end block is unreachable, it might have zero predecessors. */
  79         if (new_max == 0) {
  80                 ir_node *end_block = get_irg_end_block(irg);
  81                 if (block == end_block) {
  82                         set_irn_in(block, new_max, new_in);
  83                         return;
  84                 }
  85         }
  86
  87         new_block = new_r_Block(irg, new_max, new_in);
  88         block_entity = get_Block_entity(block);
  89         if (block_entity)
  90                 set_Block_entity(new_block, block_entity);
  91
  92         /* 2. Remove inputs on Phis, where the block input is Bad. */
  93         for (phi = get_Block_phis(block); phi != NULL; phi = next) {
  94                 ir_node *new_phi;
  95
  96                 next = get_Phi_next(phi);
  97                 assert(get_irn_arity(phi) == max);
  98
  99                 for (i = j = 0; i < max; ++i) {
 100                         ir_node *const block_pred = get_Block_cfgpred(block, i);
 101                         if (!is_Bad(block_pred)) {
 102                                 ir_node *pred = get_irn_n(phi, i);
 103                                 new_in[j++] = pred;
 104                         }
 105                 }
 106                 assert(j == new_max);
 107
 108                 new_phi = new_r_Phi(new_block, new_max, new_in, get_irn_mode(phi));
 109                 exchange(phi, new_phi);
 110         }
 111
 112         exchange(block, new_block);
 113 }
 114
 115 static void collect(ir_node *node, void *env)
 116 {
 117         firm_collect_block_phis(node, NULL);
 118         if (is_Block(node)) {
 119                 ir_node ***blocks_to_process = (ir_node***)env;
 120                 int        arity    = get_Block_n_cfgpreds(node);
 121                 int        non_bads = count_non_bads(node);
 122                 if (arity != non_bads)
 123                         ARR_APP1(ir_node*, *blocks_to_process, node);
 124         }
 125 }
 126
 127 void remove_bads(ir_graph *irg)
 128 {
 129         size_t i;
 130         size_t n_to_process;
 131         ir_node **blocks_to_process = NEW_ARR_F(ir_node*, 0);
 132
 133         /* build phi list per block */
 134         irg_walk_graph(irg, firm_clear_block_phis, collect, &blocks_to_process);
 135
 136         n_to_process = ARR_LEN(blocks_to_process);
 137         for (i = 0; i < n_to_process; ++i) {
 138                 ir_node *block = blocks_to_process[i];
 139                 block_remove_bads(block);
 140         }
 141         DEL_ARR_F(blocks_to_process);
 142
 143         if (n_to_process > 0) {
 144                 edges_deactivate(irg);
 145                 clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUTS);
 146                 clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
 147         }
 148         add_irg_properties(irg, IR_GRAPH_PROPERTY_NO_BADS);
 149 }