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

   1 /**
   2  * @file   beintlive_t.h
   3  * @date   10.05.2007
   4  * @author Sebastian Hack
   5  *
   6  * Principal routines for liveness and interference checks.
   7  *
   8  * Copyright (C) 2007 Universitaet Karlsruhe
   9  * Released under the GPL
  10  */
  11
  12 #ifndef _BELIVECHK_T_H
  13 #define _BELIVECHK_T_H
  14
  15 #include "irgraph_t.h"
  16 #include "irphase_t.h"
  17 #include "iredges_t.h"
  18
  19 #include "beirg_t.h"
  20 #include "besched_t.h"
  21
  22 /**
  23  * Check dominance of two nodes in the same block.
  24  * @param a The first node.
  25  * @param b The second node.
  26  * @return 1 if a comes before b in the same block or if a == b, 0 else.
  27  */
  28 static INLINE int _value_dominates_intrablock(const ir_node *a, const ir_node *b)
  29 {
  30         /* TODO: ? :  can be removed?! */
  31         sched_timestep_t as = is_Phi(a) ? 0 : sched_get_time_step(a);
  32         sched_timestep_t bs = is_Phi(b) ? 0 : sched_get_time_step(b);
  33         return as <= bs;
  34 }
  35
  36 /**
  37  * Check, if one value dominates the other.
  38  * The dominance is not strict here.
  39  * @param a The first node.
  40  * @param b The second node.
  41  * @return 1 if a dominates b or if a == b, 0 else.
  42  */
  43 static INLINE int _value_dominates(const ir_node *a, const ir_node *b)
  44 {
  45         const ir_node *block_a = get_block(a);
  46         const ir_node *block_b = get_block(b);
  47
  48         /*
  49          * a and b are not in the same block,
  50          * so dominance is determined by the dominance of the blocks.
  51          */
  52         if(block_a != block_b) {
  53                 return block_dominates(block_a, block_b);
  54         }
  55
  56         /*
  57          * Dominance is determined by the time steps of the schedule.
  58          */
  59         return _value_dominates_intrablock(a, b);
  60 }
  61
  62 /**
  63  * Check, if two values interfere.
  64  * @param lv Liveness information (in the future we should use a be_irg_t here).
  65  * @param a The first value.
  66  * @param b The second value.
  67  * @return 1, if a and b interfere, 0 if not.
  68  */
  69 static INLINE int _lv_values_interfere(const be_lv_t *lv, const ir_node *a, const ir_node *b)
  70 {
  71         int a2b = _value_dominates(a, b);
  72         int b2a = _value_dominates(b, a);
  73
  74         /* If there is no dominance relation, they do not interfere. */
  75         if((a2b | b2a) > 0) {
  76                 const ir_edge_t *edge;
  77                 ir_node *bb;
  78
  79                 /*
  80                  * Adjust a and b so, that a dominates b if
  81                  * a dominates b or vice versa.
  82                  */
  83                 if(b2a) {
  84                         const ir_node *t = a;
  85                         a = b;
  86                         b = t;
  87                 }
  88
  89                 bb = get_nodes_block(b);
  90
  91                 /*
  92                  * If a is live end in b's block it is
  93                  * live at b's definition (a dominates b)
  94                  */
  95                 if(be_is_live_end(lv, bb, a))
  96                         return 1;
  97
  98                 /*
  99                  * Look at all usages of a.
 100                  * If there's one usage of a in the block of b, then
 101                  * we check, if this use is dominated by b, if that's true
 102                  * a and b interfere. Note that b must strictly dominate the user,
 103                  * since if b is the last user of in the block, b and a do not
 104                  * interfere.
 105                  * Uses of a not in b's block can be disobeyed, because the
 106                  * check for a being live at the end of b's block is already
 107                  * performed.
 108                  */
 109                 foreach_out_edge(a, edge) {
 110                         const ir_node *user = get_edge_src_irn(edge);
 111                         if(get_nodes_block(user) == bb && !is_Phi(user) && b != user && _value_dominates(b, user))
 112                                 return 1;
 113                 }
 114         }
 115
 116         return 0;
 117 }
 118
 119
 120
 121 /**
 122  * Check if a node dominates a use.
 123  * Note that the use of a phi is in its corresponding predecessor.
 124  * @param irn  The node.
 125  * @param edge The use.
 126  * @return     1, if @p irn dominates the use @p edge.
 127  */
 128 static INLINE int _dominates_use(const ir_node *irn, const ir_edge_t *edge)
 129 {
 130         ir_node *use = get_edge_src_irn(edge);
 131
 132         if (is_Phi(use)) {
 133                 int pos         = get_edge_src_pos(edge);
 134                 ir_node *phi_bl = get_nodes_block(use);
 135                 ir_node *use_bl = get_Block_cfgpred_block(phi_bl, pos);
 136                 ir_node *irn_bl = get_nodes_block(irn);
 137                 return block_dominates(irn_bl, use_bl);
 138         }
 139
 140         return _value_dominates(irn, use);
 141 }
 142
 143 /**
 144  * Check if a node strictly dominates a use.
 145  * Note that the use of a phi is in its corresponding predecessor.
 146  * @param irn  The node.
 147  * @param edge The use.
 148  * @return     1, if @p irn strictly dominates the use @p edge.
 149  */
 150 static INLINE int _strictly_dominates_use(const ir_node *irn, const ir_edge_t *edge)
 151 {
 152         return get_edge_src_irn(edge) != irn && _dominates_use(irn, edge);
 153 }
 154
 155 /**
 156  * Check, if a node is live in front of another.
 157  * @param birg  The backend irg.
 158  * @param irn   The node.
 159  * @param where The location to check for.
 160  * @return      1, if @p irn is live in front of @p where.
 161  */
 162 static INLINE int _be_lv_chk_before_irn(const be_irg_t *birg, const ir_node *irn, const ir_node *where)
 163 {
 164         const be_lv_t *lv = be_get_birg_liveness(birg);
 165         const ir_edge_t *edge;
 166
 167         /* the node must strictly dominate the location, else it cannot be live there. */
 168         if (!_value_dominates(irn, where) || irn == where)
 169                 return 0;
 170
 171         /*
 172          * now that it is clear that it strictly dominates the location it is surely live
 173          * if it is also live end at the block.
 174          */
 175         if (be_is_live_end(lv, get_nodes_block(where), irn))
 176                 return 1;
 177
 178         /*
 179          * If the node is not live out, we have to check if there
 180          * is a use which is dominated by the location.
 181          */
 182         foreach_out_edge (irn, edge) {
 183                 if (_dominates_use(where, edge))
 184                         return 1;
 185         }
 186
 187         return 0;
 188 }
 189
 190 /**
 191  * Check, if a node is live after another node.
 192  * @param birg  The backend irg.
 193  * @param irn   The node.
 194  * @param where The location to check for.
 195  * @return      1, if @p irn is live after @p where.
 196  */
 197 static INLINE int _be_lv_chk_after_irn(const be_irg_t *birg, const ir_node *irn, const ir_node *where)
 198 {
 199         const be_lv_t *lv = be_get_birg_liveness(birg);
 200         const ir_edge_t *edge;
 201
 202         if (!_value_dominates(irn, where))
 203                 return 0;
 204
 205         if (be_is_live_end(lv, get_nodes_block(where), irn))
 206                 return 1;
 207
 208         foreach_out_edge (irn, edge) {
 209                 if (_strictly_dominates_use(where, edge))
 210                         return 1;
 211         }
 212
 213         return 0;
 214 }
 215
 216 #define value_dominates_intrablock(a, b)         _value_dominates_intrablock(a, b)
 217 #define value_dominates(a, b)                    _value_dominates(a, b)
 218 #define values_interfere(birg, a, b)             _lv_values_interfere(be_get_birg_liveness(birg), a, b)
 219 #define dominates_use(a, e)                      _dominates_use(a, e)
 220 #define strictly_dominates_use(a, e)             _strictly_dominates_use(a, e)
 221 #define be_lv_chk_before_irn(birg, a, b)         _be_lv_chk_before_irn(birg, a, b)
 222 #define be_lv_chk_after_irn(birg, a, b)          _be_lv_chk_after_irn(birg, a, b)
 223
 224 #endif /* _BELIVECHK_T_H */