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 "iredges_t.h"
  17
  18 #include "statev.h"
  19
  20 #include "beirg.h"
  21 #include "besched.h"
  22 #include "belive_t.h"
  23
  24 /**
  25  * Check dominance of two nodes in the same block.
  26  * @param a The first node.
  27  * @param b The second node.
  28  * @return 1 if a comes before b in the same block or if a == b, 0 else.
  29  */
  30 static inline int _value_dominates_intrablock(const ir_node *a, const ir_node *b)
  31 {
  32         /* TODO: ? :  can be removed?! */
  33         sched_timestep_t as = sched_is_scheduled(a) ? sched_get_time_step(a) : 0;
  34         sched_timestep_t bs = sched_is_scheduled(b) ? sched_get_time_step(b) : 0;
  35         return as <= bs;
  36 }
  37
  38 /**
  39  * Check strict dominance of two nodes in the same block.
  40  * @param a The first node.
  41  * @param b The second node.
  42  * @return 1 if a comes before b in the same block, 0 else.
  43  */
  44 static inline int _value_strictly_dominates_intrablock(const ir_node *a, const ir_node *b)
  45 {
  46         /* TODO: ? :  can be removed?! */
  47         sched_timestep_t as = sched_is_scheduled(a) ? sched_get_time_step(a) : 0;
  48         sched_timestep_t bs = sched_is_scheduled(b) ? sched_get_time_step(b) : 0;
  49         return as < bs;
  50 }
  51
  52 /**
  53  * Check, if one value dominates the other.
  54  * The dominance is not strict here.
  55  * @param a The first node.
  56  * @param b The second node.
  57  * @return 1 if a dominates b or if a == b, 0 else.
  58  */
  59 static inline int _value_dominates(const ir_node *a, const ir_node *b)
  60 {
  61         const ir_node *block_a = get_block_const(a);
  62         const ir_node *block_b = get_block_const(b);
  63
  64         /*
  65          * a and b are not in the same block,
  66          * so dominance is determined by the dominance of the blocks.
  67          */
  68         if(block_a != block_b) {
  69                 return block_dominates(block_a, block_b);
  70         }
  71
  72         /*
  73          * Dominance is determined by the time steps of the schedule.
  74          */
  75         return _value_dominates_intrablock(a, b);
  76 }
  77
  78 /**
  79  * Check, if one value dominates the other.
  80  * The dominance is strict here.
  81  * @param a The first node.
  82  * @param b The second node.
  83  * @return 1 if a dominates b, 0 else.
  84  */
  85 static inline int _value_strictly_dominates(const ir_node *a, const ir_node *b)
  86 {
  87         const ir_node *block_a = get_block_const(a);
  88         const ir_node *block_b = get_block_const(b);
  89
  90         /*
  91          * a and b are not in the same block,
  92          * so dominance is determined by the dominance of the blocks.
  93          */
  94         if(block_a != block_b) {
  95                 return block_dominates(block_a, block_b);
  96         }
  97
  98         /*
  99          * Dominance is determined by the time steps of the schedule.
 100          */
 101         return _value_strictly_dominates_intrablock(a, b);
 102 }
 103
 104 /**
 105  * Check, if two values interfere.
 106  * @param lv Liveness information
 107  * @param a The first value.
 108  * @param b The second value.
 109  * @return 1, if a and b interfere, 0 if not.
 110  */
 111 static inline int be_values_interfere(const be_lv_t *lv, const ir_node *a, const ir_node *b)
 112 {
 113         int a2b = _value_dominates(a, b);
 114         int b2a = _value_dominates(b, a);
 115         int res = 0;
 116
 117         /*
 118          * Adjust a and b so, that a dominates b if
 119          * a dominates b or vice versa.
 120          */
 121         if(b2a) {
 122                 const ir_node *t = a;
 123                 a = b;
 124                 b = t;
 125                 a2b = 1;
 126         }
 127
 128         /* If there is no dominance relation, they do not interfere. */
 129         if(a2b) {
 130                 ir_node *bb = get_nodes_block(b);
 131
 132                 /*
 133                  * If a is live end in b's block it is
 134                  * live at b's definition (a dominates b)
 135                  */
 136                 if(be_is_live_end(lv, bb, a)) {
 137                         res = 1;
 138                         goto end;
 139                 }
 140
 141                 /*
 142                  * Look at all usages of a.
 143                  * If there's one usage of a in the block of b, then
 144                  * we check, if this use is dominated by b, if that's true
 145                  * a and b interfere. Note that b must strictly dominate the user,
 146                  * since if b is the last user of in the block, b and a do not
 147                  * interfere.
 148                  * Uses of a not in b's block can be disobeyed, because the
 149                  * check for a being live at the end of b's block is already
 150                  * performed.
 151                  */
 152                 foreach_out_edge(a, edge) {
 153                         const ir_node *user = get_edge_src_irn(edge);
 154                         if(get_nodes_block(user) == bb && !is_Phi(user) && _value_strictly_dominates(b, user)) {
 155                                 res = 1;
 156                                 goto end;
 157                         }
 158                 }
 159         }
 160
 161 end:
 162         return res;
 163 }
 164
 165
 166
 167 /**
 168  * Check if a node dominates a use.
 169  * Note that the use of a phi is in its corresponding predecessor.
 170  * @param irn  The node.
 171  * @param edge The use.
 172  * @return     1, if @p irn dominates the use @p edge.
 173  */
 174 static inline int _dominates_use(const ir_node *irn, const ir_edge_t *edge)
 175 {
 176         ir_node *use = get_edge_src_irn(edge);
 177
 178         if (is_Phi(use)) {
 179                 int pos         = get_edge_src_pos(edge);
 180                 ir_node *phi_bl = get_nodes_block(use);
 181                 ir_node *use_bl = get_Block_cfgpred_block(phi_bl, pos);
 182                 ir_node *irn_bl = get_nodes_block(irn);
 183                 return block_dominates(irn_bl, use_bl);
 184         }
 185
 186         return _value_dominates(irn, use);
 187 }
 188
 189 /**
 190  * Check if a node strictly dominates a use.
 191  * Note that the use of a phi is in its corresponding predecessor.
 192  * @param irn  The node.
 193  * @param edge The use.
 194  * @return     1, if @p irn strictly dominates the use @p edge.
 195  */
 196 static inline int _strictly_dominates_use(const ir_node *irn, const ir_edge_t *edge)
 197 {
 198         return get_edge_src_irn(edge) != irn && _dominates_use(irn, edge);
 199 }
 200
 201 /**
 202  * Check, if a node is live in front of another.
 203  * @param irg   The backend irg.
 204  * @param irn   The node.
 205  * @param where The location to check for.
 206  * @return      1, if @p irn is live in front of @p where.
 207  */
 208 static inline int _be_lv_chk_before_irn(ir_graph *irg, const ir_node *irn,
 209                                         const ir_node *where)
 210 {
 211         const be_lv_t *lv = be_get_irg_liveness(irg);
 212
 213         /* the node must strictly dominate the location, else it cannot be live there. */
 214         if (!_value_dominates(irn, where) || irn == where)
 215                 return 0;
 216
 217         /*
 218          * now that it is clear that it strictly dominates the location it is surely live
 219          * if it is also live end at the block.
 220          */
 221         if (be_is_live_end(lv, get_nodes_block(where), irn))
 222                 return 1;
 223
 224         /*
 225          * If the node is not live out, we have to check if there
 226          * is a use which is dominated by the location.
 227          */
 228         foreach_out_edge (irn, edge) {
 229                 if (_dominates_use(where, edge))
 230                         return 1;
 231         }
 232
 233         return 0;
 234 }
 235
 236 /**
 237  * Check, if a node is live after another node.
 238  * @param irg   The backend irg.
 239  * @param irn   The node.
 240  * @param where The location to check for.
 241  * @return      1, if @p irn is live after @p where.
 242  */
 243 static inline int _be_lv_chk_after_irn(ir_graph *irg, const ir_node *irn,
 244                                        const ir_node *where)
 245 {
 246         const be_lv_t *lv = be_get_irg_liveness(irg);
 247
 248         if (!_value_dominates(irn, where))
 249                 return 0;
 250
 251         if (be_is_live_end(lv, get_nodes_block(where), irn))
 252                 return 1;
 253
 254         foreach_out_edge (irn, edge) {
 255                 if (_strictly_dominates_use(where, edge))
 256                         return 1;
 257         }
 258
 259         return 0;
 260 }
 261
 262 #define value_dominates_intrablock(a, b)         _value_dominates_intrablock(a, b)
 263 #define value_dominates(a, b)                    _value_dominates(a, b)
 264 #define dominates_use(a, e)                      _dominates_use(a, e)
 265 #define strictly_dominates_use(a, e)             _strictly_dominates_use(a, e)
 266 #define be_lv_chk_before_irn(irg, a, b)         _be_lv_chk_before_irn(irg, a, b)
 267 #define be_lv_chk_after_irn(irg, a, b)          _be_lv_chk_after_irn(irg, a, b)
 268
 269 #endif