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 FIRM_IMPL2(is_live_in, int, const ir_node *, const ir_node *)
  19 FIRM_IMPL2(is_live_out, int, const ir_node *, const ir_node *)
  20
  21 /** The offset of the liveness information in a firm node. */
  22 size_t live_irn_data_offset = 0;
  23
  24 void be_liveness_init(void)
  25 {
  26         live_irn_data_offset = register_additional_node_data(sizeof(live_info_t));
  27 }
  28
  29 static INLINE void mark_live_in(ir_node *block, const ir_node *irn)
  30 {
  31         block_live_info_t *info = get_block_live_info(block);
  32         pset_insert_ptr(info->in, irn);
  33 }
  34
  35 static INLINE void mark_live_out(ir_node *block, const ir_node *irn)
  36 {
  37         block_live_info_t *info = get_block_live_info(block);
  38         pset_insert_ptr(info->out, irn);
  39 }
  40
  41 /**
  42  * Mark a node (value) live out at a certain block. Do this also
  43  * transitively, i.e. if the block is not the block of the value's
  44  * definition, all predecessors are also marked live.
  45  * @param def The node (value).
  46  * @param block The block to mark the value live out of.
  47  * @param visited A set were all visited blocks are recorded.
  48  */
  49 static void live_out_at_block(ir_node *def, ir_node *block, pset *visited)
  50 {
  51         if(pset_find_ptr(visited, block))
  52                 return;
  53
  54         pset_insert_ptr(visited, block);
  55         mark_live_out(block, def);
  56
  57         /*
  58          * If this block is not the definition block, we have to go up
  59          * further.
  60          */
  61         if(get_nodes_block(def) != block) {
  62                 int i, n;
  63
  64                 mark_live_in(block, def);
  65
  66                 for(i = 0, n = get_irn_arity(block); i < n; ++i)
  67                         live_out_at_block(def, get_nodes_block(get_irn_n(block, i)), visited);
  68         }
  69 }
  70
  71 /**
  72  * Liveness analysis for a value.
  73  * This functions is meant to be called by a firm walker, to compute the
  74  * set of all blocks a value is live in.
  75  * @param irn The node (value).
  76  * @param env Ignored.
  77  */
  78 static void liveness_for_node(ir_node *irn, void *env)
  79 {
  80         int i, n;
  81         ir_node *def_block;
  82         pset *visited;
  83
  84         /* Don't compute liveness information fornon-data nodes. */
  85         if(!is_data_node(irn))
  86                 return;
  87
  88         visited = pset_new_ptr(512);
  89         def_block = get_nodes_block(irn);
  90
  91         /* Go over all uses of the value */
  92         for(i = 0, n = get_irn_n_outs(irn); i < n; ++i) {
  93                 ir_node *use = get_irn_out(irn, i);
  94                 ir_node *use_block;
  95
  96                 /*
  97                  * If the usage is no data node, skip this use, since it does not
  98                  * affect the liveness of the node.
  99                  */
 100                 if(!is_data_node(use))
 101                         continue;
 102
 103                 /* Get the block where the usage is in. */
 104                 use_block = get_nodes_block(use);
 105
 106                 /*
 107                  * If the block of the definition equals the use block, we can skip
 108                  * the following computations, since this use is local to a block.
 109                  */
 110                 if(def_block == use_block)
 111                         continue;
 112
 113                 /*
 114                  * If the use is a phi function, determine the corresponding block
 115                  * through which the value reaches the phi function and mark the
 116                  * value as live out of that block.
 117                  */
 118                 if(is_Phi(use)) {
 119                         int i, n;
 120
 121                         /* Mark the node as a phi operand, since a use by a phi was found. */
 122                         get_node_live_info(irn)->is_phi_op = 1;
 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         info->in = pset_new_ptr(128);
 155         info->out = pset_new_ptr(128);
 156 }
 157
 158
 159 static void liveness_dump(ir_node *block, void *env)
 160 {
 161         FILE *f = env;
 162         block_live_info_t *info = get_block_live_info(block);
 163
 164         assert(is_Block(block) && "Need a block here");
 165         ir_fprintf(f, "liveness at block %n\n", block);
 166         ir_fprintf(f, "\tlive  in: %*n\n", pset_iterator, info->in);
 167         ir_fprintf(f, "\tlive out: %*n\n", pset_iterator, info->out);
 168 }
 169
 170 void be_liveness_dump(FILE *f, ir_graph *irg)
 171 {
 172         irg_block_walk_graph(irg, liveness_dump, NULL, f);
 173 }
 174
 175 void be_liveness(ir_graph *irg)
 176 {
 177         irg_block_walk_graph(irg, create_sets, NULL, NULL);
 178         irg_walk_graph(irg, liveness_for_node, NULL, NULL);
 179 }