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 "besched.h"
  16 #include "belive_t.h"
  17 #include "iredges_t.h"
  18
  19 /**
  20  * Check dominance of two nodes in the same block.
  21  * @param a The first node.
  22  * @param b The second node.
  23  * @return 1 if a comes before b in the same block or if a == b, 0 else.
  24  */
  25 static inline int _value_dominates_intrablock(const ir_node *a, const ir_node *b)
  26 {
  27         assert(sched_is_scheduled(a));
  28         assert(sched_is_scheduled(b));
  29         sched_timestep_t const as = sched_get_time_step(a);
  30         sched_timestep_t const bs = sched_get_time_step(b);
  31         return as <= bs;
  32 }
  33
  34 /**
  35  * Check strict dominance of two nodes in the same block.
  36  * @param a The first node.
  37  * @param b The second node.
  38  * @return 1 if a comes before b in the same block, 0 else.
  39  */
  40 static inline int _value_strictly_dominates_intrablock(const ir_node *a, const ir_node *b)
  41 {
  42         assert(sched_is_scheduled(a));
  43         assert(sched_is_scheduled(b));
  44         sched_timestep_t const as = sched_get_time_step(a);
  45         sched_timestep_t const bs = sched_get_time_step(b);
  46         return as < bs;
  47 }
  48
  49 /**
  50  * Check, if one value dominates the other.
  51  * The dominance is not strict here.
  52  * @param a The first node.
  53  * @param b The second node.
  54  * @return 1 if a dominates b or if a == b, 0 else.
  55  */
  56 static inline int _value_dominates(const ir_node *a, const ir_node *b)
  57 {
  58         const ir_node *block_a = get_block_const(a);
  59         const ir_node *block_b = get_block_const(b);
  60
  61         /*
  62          * a and b are not in the same block,
  63          * so dominance is determined by the dominance of the blocks.
  64          */
  65         if(block_a != block_b) {
  66                 return block_dominates(block_a, block_b);
  67         }
  68
  69         /*
  70          * Dominance is determined by the time steps of the schedule.
  71          */
  72         return _value_dominates_intrablock(a, b);
  73 }
  74
  75 /**
  76  * Check, if one value dominates the other.
  77  * The dominance is strict here.
  78  * @param a The first node.
  79  * @param b The second node.
  80  * @return 1 if a dominates b, 0 else.
  81  */
  82 static inline int _value_strictly_dominates(const ir_node *a, const ir_node *b)
  83 {
  84         const ir_node *block_a = get_block_const(a);
  85         const ir_node *block_b = get_block_const(b);
  86
  87         /*
  88          * a and b are not in the same block,
  89          * so dominance is determined by the dominance of the blocks.
  90          */
  91         if(block_a != block_b) {
  92                 return block_dominates(block_a, block_b);
  93         }
  94
  95         /*
  96          * Dominance is determined by the time steps of the schedule.
  97          */
  98         return _value_strictly_dominates_intrablock(a, b);
  99 }
 100
 101 /**
 102  * Check, if two values interfere.
 103  * @param lv Liveness information
 104  * @param a The first value.
 105  * @param b The second value.
 106  * @return 1, if a and b interfere, 0 if not.
 107  */
 108 static inline int be_values_interfere(const be_lv_t *lv, const ir_node *a, const ir_node *b)
 109 {
 110         int a2b = _value_dominates(a, b);
 111         int b2a = _value_dominates(b, a);
 112         int res = 0;
 113
 114         /*
 115          * Adjust a and b so, that a dominates b if
 116          * a dominates b or vice versa.
 117          */
 118         if(b2a) {
 119                 const ir_node *t = a;
 120                 a = b;
 121                 b = t;
 122                 a2b = 1;
 123         }
 124
 125         /* If there is no dominance relation, they do not interfere. */
 126         if(a2b) {
 127                 ir_node *bb = get_nodes_block(b);
 128
 129                 /*
 130                  * If a is live end in b's block it is
 131                  * live at b's definition (a dominates b)
 132                  */
 133                 if(be_is_live_end(lv, bb, a)) {
 134                         res = 1;
 135                         goto end;
 136                 }
 137
 138                 /*
 139                  * Look at all usages of a.
 140                  * If there's one usage of a in the block of b, then
 141                  * we check, if this use is dominated by b, if that's true
 142                  * a and b interfere. Note that b must strictly dominate the user,
 143                  * since if b is the last user of in the block, b and a do not
 144                  * interfere.
 145                  * Uses of a not in b's block can be disobeyed, because the
 146                  * check for a being live at the end of b's block is already
 147                  * performed.
 148                  */
 149                 foreach_out_edge(a, edge) {
 150                         const ir_node *user = get_edge_src_irn(edge);
 151                         if(get_nodes_block(user) == bb && !is_Phi(user) && _value_strictly_dominates(b, user)) {
 152                                 res = 1;
 153                                 goto end;
 154                         }
 155                 }
 156         }
 157
 158 end:
 159         return res;
 160 }
 161
 162 #define value_dominates(a, b) _value_dominates(a, b)
 163
 164 #endif