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 "beutil.h"
  18 #include "iredges_t.h"
  19
  20 #define value_dominates(a, b) _value_dominates(a, b)
  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         assert(sched_is_scheduled(a));
  31         assert(sched_is_scheduled(b));
  32         sched_timestep_t const as = sched_get_time_step(a);
  33         sched_timestep_t const bs = sched_get_time_step(b);
  34         return as <= bs;
  35 }
  36
  37 /**
  38  * Check strict dominance of two nodes in the same block.
  39  * @param a The first node.
  40  * @param b The second node.
  41  * @return 1 if a comes before b in the same block, 0 else.
  42  */
  43 static inline int _value_strictly_dominates_intrablock(const ir_node *a, const ir_node *b)
  44 {
  45         assert(sched_is_scheduled(a));
  46         assert(sched_is_scheduled(b));
  47         sched_timestep_t const as = sched_get_time_step(a);
  48         sched_timestep_t const bs = sched_get_time_step(b);
  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 #endif