nsz Git - libfirm/blob - ir/be/belive.c

   1 /**
   2  * Interblock liveness analysis.
   3  * @author Sebastian Hack
   4  * @date 6.12.2004
   5  */
   6 #ifdef HAVE_CONFIG_H
   7 #include "config.h"
   8 #endif
   9
  10 #include "impl.h"
  11 #include "irouts.h"
  12 #include "irgwalk.h"
  13 #include "irprintf_t.h"
  14
  15 #include "beutil.h"
  16 #include "belive_t.h"
  17
  18 #define DEFAULT_LIVE_SET_SIZE                           8
  19
  20 FIRM_IMPL2(is_live_in, int, const ir_node *, const ir_node *)
  21 FIRM_IMPL2(is_live_out, int, const ir_node *, const ir_node *)
  22 FIRM_IMPL2(is_live_end, int, const ir_node *, const ir_node *)
  23
  24 /** The offset of the liveness information in a firm node. */
  25 size_t live_irn_data_offset = 0;
  26
  27 void be_liveness_init(void)
  28 {
  29         live_irn_data_offset = register_additional_node_data(sizeof(live_info_t));
  30 }
  31
  32 static INLINE void mark_live_in(ir_node *block, const ir_node *irn)
  33 {
  34         block_live_info_t *info = get_block_live_info(block);
  35         pset_insert_ptr(info->in, irn);
  36 }
  37
  38 static INLINE void mark_live_out(ir_node *block, const ir_node *irn)
  39 {
  40         block_live_info_t *info = get_block_live_info(block);
  41         pset_insert_ptr(info->out, irn);
  42 }
  43
  44 static INLINE void mark_live_end(ir_node *block, const ir_node *irn)
  45 {
  46         block_live_info_t *info = get_block_live_info(block);
  47         pset_insert_ptr(info->end, irn);
  48 }
  49
  50 /**
  51  * Mark a node (value) live out at a certain block. Do this also
  52  * transitively, i.e. if the block is not the block of the value's
  53  * definition, all predecessors are also marked live.
  54  * @param def The node (value).
  55  * @param block The block to mark the value live out of.
  56  * @param visited A set were all visited blocks are recorded.
  57  * @param is_true_out Is the node real out there or only live at the end
  58  * of the block.
  59  */
  60 static void live_end_at_block(ir_node *def, ir_node *block,
  61                 pset *visited, int is_true_out)
  62 {
  63         mark_live_end(block, def);
  64         if(is_true_out)
  65                 mark_live_out(block, def);
  66
  67         if(!pset_find_ptr(visited, block)) {
  68
  69                 pset_insert_ptr(visited, block);
  70
  71                 /*
  72                  * If this block is not the definition block, we have to go up
  73                  * further.
  74                  */
  75                 if(get_nodes_block(def) != block) {
  76                         int i, n;
  77
  78                         mark_live_in(block, def);
  79
  80                         for(i = 0, n = get_irn_arity(block); i < n; ++i)
  81                                 live_end_at_block(def, get_nodes_block(get_irn_n(block, i)), visited, 1);
  82                 }
  83
  84         }
  85 }
  86
  87 /**
  88  * Liveness analysis for a value.
  89  * This functions is meant to be called by a firm walker, to compute the
  90  * set of all blocks a value is live in.
  91  * @param irn The node (value).
  92  * @param env Ignored.
  93  */
  94 static void liveness_for_node(ir_node *irn, void *env)
  95 {
  96         int i, n;
  97         ir_node *def_block;
  98         pset *visited;
  99
 100         /* Don't compute liveness information for non-data nodes. */
 101         if(!is_data_node(irn))
 102                 return;
 103
 104         visited = pset_new_ptr(512);
 105         def_block = get_nodes_block(irn);
 106
 107         /* Go over all uses of the value */
 108         for(i = 0, n = get_irn_n_outs(irn); i < n; ++i) {
 109                 ir_node *use = get_irn_out(irn, i);
 110                 ir_node *use_block;
 111
 112                 /*
 113                  * If the usage is no data node, skip this use, since it does not
 114                  * affect the liveness of the node.
 115                  */
 116                 if(!is_data_node(use))
 117                         continue;
 118
 119                 /* Get the block where the usage is in. */
 120                 use_block = get_nodes_block(use);
 121
 122                 /*
 123                  * If the use is a phi function, determine the corresponding block
 124                  * through which the value reaches the phi function and mark the
 125                  * value as live out of that block.
 126                  */
 127                 if(is_Phi(use)) {
 128                         int i, n;
 129
 130                         /* Mark the node as a phi operand, since a use by a phi was found. */
 131                         get_node_live_info(irn)->is_phi_op = 1;
 132
 133                         for(i = 0, n = get_irn_arity(use); i < n; ++i) {
 134                                 if(get_irn_n(use, i) == irn) {
 135                                         ir_node *pred_block = get_nodes_block(get_irn_n(use_block, i));
 136                                         live_end_at_block(irn, pred_block, visited, 0);
 137                                 }
 138                         }
 139                 }
 140
 141                 /*
 142                  * Else, the value is live in at this block. Mark it and call live
 143                  * out on the predecessors.
 144                  */
 145                 else if(def_block != use_block) {
 146                         int i, n;
 147
 148                         mark_live_in(use_block, irn);
 149
 150                         for(i = 0, n = get_irn_arity(use_block); i < n; ++i) {
 151                                 ir_node *pred_block = get_nodes_block(get_irn_n(use_block, i));
 152                                 live_end_at_block(irn, pred_block, visited, 1);
 153                         }
 154                 }
 155         }
 156
 157         del_pset(visited);
 158 }
 159
 160 static void create_sets(ir_node *block, void *env)
 161 {
 162         block_live_info_t *info = get_block_live_info(block);
 163         info->in = pset_new_ptr(DEFAULT_LIVE_SET_SIZE);
 164         info->out = pset_new_ptr(DEFAULT_LIVE_SET_SIZE);
 165         info->end = pset_new_ptr(DEFAULT_LIVE_SET_SIZE);
 166 }
 167
 168
 169 static void liveness_dump(ir_node *block, void *env)
 170 {
 171         FILE *f = env;
 172         block_live_info_t *info = get_block_live_info(block);
 173
 174         assert(is_Block(block) && "Need a block here");
 175         ir_fprintf(f, "liveness at block %n\n", block);
 176         ir_fprintf(f, "\tlive  in: %*n\n", pset_iterator, info->in);
 177         ir_fprintf(f, "\tlive out: %*n\n", pset_iterator, info->out);
 178         ir_fprintf(f, "\tlive end: %*n\n", pset_iterator, info->end);
 179 }
 180
 181 void be_liveness_dump(FILE *f, ir_graph *irg)
 182 {
 183         irg_block_walk_graph(irg, liveness_dump, NULL, f);
 184 }
 185
 186 void be_liveness(ir_graph *irg)
 187 {
 188         irg_block_walk_graph(irg, create_sets, NULL, NULL);
 189         irg_walk_graph(irg, liveness_for_node, NULL, NULL);
 190 }