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

   1 /**
   2  * Interblock liveness analysis.
   3  * @author Sebastian Hack
   4  * @date   6.12.2004
   5  * @cvs-id $Id$
   6  */
   7
   8 #ifndef _BELIVE_H
   9 #define _BELIVE_H
  10
  11 #include "firm_types.h"
  12 #include "pset.h"
  13 #include "bearch_t.h"
  14
  15 #include <stdio.h>
  16
  17 typedef enum {
  18         be_lv_state_in  = 1,
  19         be_lv_state_end = 2,
  20         be_lv_state_out = 4,
  21 } be_lv_state_t;
  22
  23 typedef struct _be_lv_t be_lv_t;
  24
  25 typedef struct _be_lv_info_t be_lv_info_t;
  26
  27
  28 /**
  29  * Compute the inter block liveness for a graph.
  30  * @param irg The graph.
  31  */
  32 be_lv_t *be_liveness(ir_graph *irg);
  33
  34 /**
  35  * Check the given liveness information against a freshly computed one.
  36  */
  37 void be_liveness_check(be_lv_t *lv);
  38
  39 /**
  40  * Free the liveness information.
  41  */
  42 void be_liveness_free(be_lv_t *lv);
  43
  44 /**
  45  * Recompute the complete liveness information.
  46  */
  47 void be_liveness_recompute(be_lv_t *lv);
  48
  49 /**
  50  * Update the liveness information for a single node.
  51  * It is irrelevant if there is liveness information present for the node.
  52  * The liveness information for the node is firstly deleted and then recompute.
  53  * So, if the node is fresh and never recorded inf the liveness information
  54  * before, it is more efficient to call be_liveness_introduce().
  55  */
  56 void be_liveness_update(be_lv_t *lv, ir_node *irn);
  57
  58 /**
  59  * Remove a node from the liveness information.
  60  */
  61 void be_liveness_remove(be_lv_t *lv, ir_node *irn);
  62
  63 /**
  64  * Introduce a new node to the liveness information.
  65  * The new irn is not deleted from any block's liveness information, so it must be fresh!
  66  * @param lv The liveness info.
  67  * @param irn The node.
  68  */
  69 void be_liveness_introduce(be_lv_t *lv, ir_node *irn);
  70
  71 /**
  72  * Dump the liveness information for a graph.
  73  * @param f The output.
  74  * @param irg The graph.
  75  */
  76 void be_liveness_dump(const be_lv_t *lv, FILE *f);
  77
  78 /**
  79  * Dump the liveness information for a graph.
  80  * @param irg The graph.
  81  * @param cls_name A string used as substring in the filename.
  82  */
  83 void be_liveness_dumpto(const be_lv_t *lv, const char *cls_name);
  84
  85 /**
  86  * Check, if a node is live in at a block.
  87  * @param block The block.
  88  * @param irn The node to check for.
  89  * @return 1, if @p irn is live at the entrance of @p block, 0 if not.
  90  */
  91 int (be_is_live_in)(const be_lv_t *lv, const ir_node *block, const ir_node *irn);
  92
  93 /**
  94  * Check, if a node is live out at a block.
  95  * @param block The block.
  96  * @param irn The node to check for.
  97  * @return 1, if @p irn is live at the exit of @p block, 0 if not.
  98  */
  99 int (be_is_live_out)(const be_lv_t *lv, const ir_node *block, const ir_node *irn);
 100
 101 /**
 102  * Check, if a node is live at the end of a block.
 103  * @param block The block.
 104  * @param irn The node to check for.
 105  * @return 1, if @p irn is live at the end of the block, 0 if not.
 106  */
 107 int (be_is_live_end)(const be_lv_t *lv, const ir_node *block, const ir_node *irn);
 108
 109 /**
 110  * Check, if the SSA dominance property is fulfilled.
 111  * @param irg The graph.
 112  */
 113 void be_check_dominance(ir_graph *irg);
 114
 115 /**
 116  * The liveness transfer function.
 117  * Updates a live set over a single step from a given node to its predecessor.
 118  * Everything defined at the node is removed from the set, the uses of the node get inserted.
 119  * @param arch_env The architecture environment.
 120  * @param cls      The register class to consider.
 121  * @param irn      The node at which liveness should be computed.
 122  * @param live     The set of nodes live before @p irn. This set gets modified by updating it to
 123  *                 the nodes live after irn.
 124  * @return live.
 125  */
 126 pset *be_liveness_transfer(const arch_env_t *arch_env, const arch_register_class_t *cls, ir_node *irn, pset *live);
 127
 128 /**
 129  * Put all node live at the end of a block into a set.
 130  * @param arch_env The architecture environment.
 131  * @param cls      The register class to consider.
 132  * @param bl       The block.
 133  * @param live     The set to put them into.
 134  * @return live.
 135  */
 136 pset *be_liveness_end_of_block(const be_lv_t *lv, const arch_env_t *arch_env, const arch_register_class_t *cls, const ir_node *bl, pset *live);
 137
 138 /**
 139  * Compute a set of nodes which are live at another node.
 140  * @param arch_env The architecture environment.
 141  * @param cls      The register class to consider.
 142  * @param pos      The node.
 143  * @param live     The set to put them into.
 144  * @return live.
 145  */
 146 pset *be_liveness_nodes_live_at(const be_lv_t *lv, const arch_env_t *arch_env, const arch_register_class_t *cls, const ir_node *pos, pset *live);
 147
 148
 149 /**
 150  * FIXME: Need comment
 151  */
 152 void be_liveness_add_missing(be_lv_t *lv);
 153
 154 #endif /* _BELIVE_H */