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

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