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