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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @brief    Remove all Bad nodes from ir graph
   8  * @author   Andreas Zwinkau
   9  */
  10 #include "config.h"
  11
  12 #include <assert.h>
  13
  14 #include "irnode_t.h"
  15
  16 #include "irgopt.h"
  17 #include "irgmod.h"
  18 #include "irgwalk.h"
  19
  20 #include "irtools.h"
  21
  22 /**
  23  * Return the number of non-Bad predecessors of the given node.
  24  */
  25 static int count_non_bads(ir_node *node)
  26 {
  27         int arity = get_Block_n_cfgpreds(node);
  28         int count = 0;
  29         int i;
  30         for (i = 0; i < arity; ++i) {
  31                 if (!is_Bad(get_irn_n(node, i)))
  32                         ++count;
  33         }
  34         return count;
  35 }
  36
  37 /**
  38  * Block-walker, remove Bad block predecessors and shorten Phis.
  39  * Phi links must be uptodate.
  40  */
  41 static void block_remove_bads(ir_node *block)
  42 {
  43         ir_graph  *irg     = get_irn_irg(block);
  44         const int  max     = get_Block_n_cfgpreds(block);
  45         const int  new_max = count_non_bads(block);
  46         ir_node  **new_in  = ALLOCAN(ir_node*, new_max);
  47         int        i;
  48         int        j;
  49         ir_node   *new_block;
  50         ir_node   *phi;
  51         ir_node   *next;
  52         ir_entity *block_entity;
  53         assert(max >= new_max);
  54
  55         /* 1. Create a new block without Bad inputs */
  56         for (i = j = 0; i < max; ++i) {
  57                 ir_node *const block_pred = get_Block_cfgpred(block, i);
  58                 if (!is_Bad(block_pred)) {
  59                         new_in[j++] = block_pred;
  60                 }
  61         }
  62         assert(j == new_max);
  63
  64         /* If the end block is unreachable, it might have zero predecessors. */
  65         if (new_max == 0) {
  66                 ir_node *end_block = get_irg_end_block(irg);
  67                 if (block == end_block) {
  68                         set_irn_in(block, new_max, new_in);
  69                         return;
  70                 }
  71         }
  72
  73         new_block = new_r_Block(irg, new_max, new_in);
  74         block_entity = get_Block_entity(block);
  75         if (block_entity)
  76                 set_Block_entity(new_block, block_entity);
  77
  78         /* 2. Remove inputs on Phis, where the block input is Bad. */
  79         for (phi = get_Block_phis(block); phi != NULL; phi = next) {
  80                 ir_node *new_phi;
  81
  82                 next = get_Phi_next(phi);
  83                 assert(get_irn_arity(phi) == max);
  84
  85                 for (i = j = 0; i < max; ++i) {
  86                         ir_node *const block_pred = get_Block_cfgpred(block, i);
  87                         if (!is_Bad(block_pred)) {
  88                                 ir_node *pred = get_irn_n(phi, i);
  89                                 new_in[j++] = pred;
  90                         }
  91                 }
  92                 assert(j == new_max);
  93
  94                 new_phi = new_r_Phi(new_block, new_max, new_in, get_irn_mode(phi));
  95                 exchange(phi, new_phi);
  96         }
  97
  98         exchange(block, new_block);
  99 }
 100
 101 static void collect(ir_node *node, void *env)
 102 {
 103         firm_collect_block_phis(node, NULL);
 104         if (is_Block(node)) {
 105                 ir_node ***blocks_to_process = (ir_node***)env;
 106                 int        arity    = get_Block_n_cfgpreds(node);
 107                 int        non_bads = count_non_bads(node);
 108                 if (arity != non_bads)
 109                         ARR_APP1(ir_node*, *blocks_to_process, node);
 110         }
 111 }
 112
 113 void remove_bads(ir_graph *irg)
 114 {
 115         size_t i;
 116         size_t n_to_process;
 117         ir_node **blocks_to_process = NEW_ARR_F(ir_node*, 0);
 118
 119         /* build phi list per block */
 120         irg_walk_graph(irg, firm_clear_block_phis, collect, &blocks_to_process);
 121
 122         n_to_process = ARR_LEN(blocks_to_process);
 123         for (i = 0; i < n_to_process; ++i) {
 124                 ir_node *block = blocks_to_process[i];
 125                 block_remove_bads(block);
 126         }
 127         DEL_ARR_F(blocks_to_process);
 128
 129         if (n_to_process > 0) {
 130                 edges_deactivate(irg);
 131                 clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUTS);
 132                 clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE);
 133         }
 134         add_irg_properties(irg, IR_GRAPH_PROPERTY_NO_BADS);
 135 }