4 * @author Sebastian Hack
6 * Principal routines for liveness and interference checks.
8 * Copyright (C) 2007 Universitaet Karlsruhe
9 * Released under the GPL
12 #ifndef _BELIVECHK_T_H
13 #define _BELIVECHK_T_H
17 #include "iredges_t.h"
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.
25 static inline int _value_dominates_intrablock(const ir_node *a, const ir_node *b)
27 /* TODO: ? : can be removed?! */
28 sched_timestep_t as = sched_is_scheduled(a) ? sched_get_time_step(a) : 0;
29 sched_timestep_t bs = sched_is_scheduled(b) ? sched_get_time_step(b) : 0;
34 * Check strict dominance of two nodes in the same block.
35 * @param a The first node.
36 * @param b The second node.
37 * @return 1 if a comes before b in the same block, 0 else.
39 static inline int _value_strictly_dominates_intrablock(const ir_node *a, const ir_node *b)
41 /* TODO: ? : can be removed?! */
42 sched_timestep_t as = sched_is_scheduled(a) ? sched_get_time_step(a) : 0;
43 sched_timestep_t bs = sched_is_scheduled(b) ? sched_get_time_step(b) : 0;
48 * Check, if one value dominates the other.
49 * The dominance is not strict here.
50 * @param a The first node.
51 * @param b The second node.
52 * @return 1 if a dominates b or if a == b, 0 else.
54 static inline int _value_dominates(const ir_node *a, const ir_node *b)
56 const ir_node *block_a = get_block_const(a);
57 const ir_node *block_b = get_block_const(b);
60 * a and b are not in the same block,
61 * so dominance is determined by the dominance of the blocks.
63 if(block_a != block_b) {
64 return block_dominates(block_a, block_b);
68 * Dominance is determined by the time steps of the schedule.
70 return _value_dominates_intrablock(a, b);
74 * Check, if one value dominates the other.
75 * The dominance is strict here.
76 * @param a The first node.
77 * @param b The second node.
78 * @return 1 if a dominates b, 0 else.
80 static inline int _value_strictly_dominates(const ir_node *a, const ir_node *b)
82 const ir_node *block_a = get_block_const(a);
83 const ir_node *block_b = get_block_const(b);
86 * a and b are not in the same block,
87 * so dominance is determined by the dominance of the blocks.
89 if(block_a != block_b) {
90 return block_dominates(block_a, block_b);
94 * Dominance is determined by the time steps of the schedule.
96 return _value_strictly_dominates_intrablock(a, b);
100 * Check, if two values interfere.
101 * @param lv Liveness information
102 * @param a The first value.
103 * @param b The second value.
104 * @return 1, if a and b interfere, 0 if not.
106 static inline int be_values_interfere(const be_lv_t *lv, const ir_node *a, const ir_node *b)
108 int a2b = _value_dominates(a, b);
109 int b2a = _value_dominates(b, a);
113 * Adjust a and b so, that a dominates b if
114 * a dominates b or vice versa.
117 const ir_node *t = a;
123 /* If there is no dominance relation, they do not interfere. */
125 ir_node *bb = get_nodes_block(b);
128 * If a is live end in b's block it is
129 * live at b's definition (a dominates b)
131 if(be_is_live_end(lv, bb, a)) {
137 * Look at all usages of a.
138 * If there's one usage of a in the block of b, then
139 * we check, if this use is dominated by b, if that's true
140 * a and b interfere. Note that b must strictly dominate the user,
141 * since if b is the last user of in the block, b and a do not
143 * Uses of a not in b's block can be disobeyed, because the
144 * check for a being live at the end of b's block is already
147 foreach_out_edge(a, edge) {
148 const ir_node *user = get_edge_src_irn(edge);
149 if(get_nodes_block(user) == bb && !is_Phi(user) && _value_strictly_dominates(b, user)) {
160 #define value_dominates(a, b) _value_dominates(a, b)