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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief       Scheduling utilities for nodes in Blocks and Blocks.
  23  * @author      Sebastian Hack
  24  * @version     $Id$
  25  */
  26 #ifndef FIRM_BE_BESCHED_T_H
  27 #define FIRM_BE_BESCHED_T_H
  28
  29 #define SCHED_INITIAL_GRANULARITY (1 << 14)
  30
  31 #include "list.h"
  32 #include "irnode_t.h"
  33 #include "irgraph_t.h"
  34 #include "irphase_t.h"
  35 #include "irphases_t.h"
  36
  37 #include "beutil.h"
  38 #include "besched.h"
  39 #include "beinfo.h"
  40
  41 #define _sched_entry(list_head)             (list_entry(list_head, sched_info_t, list))
  42 #define get_irn_sched_info(irn)             (&be_get_info(skip_Proj_const(irn))->sched_info)
  43 #define get_sched_info_irn(irg, sched_info) get_idx_irn((irg), (sched_info)->idx)
  44
  45 /**
  46  * Returns non-zero if schedule information is available
  47  * for a given graph.
  48  * @param irg  The graph.
  49  */
  50 static inline int _have_sched_info(const ir_graph *irg)
  51 {
  52         return be_info_initialized(irg);
  53 }
  54
  55 /**
  56  * Check, if the node is scheduled.
  57  * @param irn The node.
  58  * @return 1, if the node is scheduled, 0 if not.
  59  */
  60 static inline int _sched_is_scheduled(const ir_node *irn)
  61 {
  62         return get_irn_sched_info(irn)->scheduled;
  63 }
  64
  65 /**
  66  * Get the time step of an irn in a schedule.
  67  * @param irn The node.
  68  * @return The time step in the schedule.
  69  */
  70 static inline int _sched_get_time_step(const ir_node *irn)
  71 {
  72         assert(_sched_is_scheduled(irn));
  73         return get_irn_sched_info(irn)->time_step;
  74 }
  75
  76 /**
  77  * Checks, if a node is to appear in a schedule. Such nodes either
  78  * consume real data (mode datab) or produce such.
  79  * @param irn The node to check for.
  80  * @return 1, if the node consumes/produces data, false if not.
  81  */
  82 static inline int to_appear_in_schedule(const ir_node *irn)
  83 {
  84         switch(get_irn_opcode(irn)) {
  85                 case iro_Start:
  86                 case iro_Jmp:
  87                 case iro_Break:
  88                         return 1;
  89                 case iro_Proj:
  90                         return 0;
  91                 default:
  92                         return is_data_node(irn);
  93         }
  94 }
  95
  96 /**
  97  * Check, if an ir_node has a scheduling successor.
  98  * @param irn The ir node.
  99  * @return 1, if the node has a scheduling successor, 0 if not.
 100  */
 101 static inline int _sched_has_next(const ir_node *irn)
 102 {
 103         const ir_node *block = is_Block(irn) ? irn : get_nodes_block(irn);
 104         const sched_info_t *info = get_irn_sched_info(irn);
 105         const sched_info_t *block_info = get_irn_sched_info(block);
 106         return info->list.next != &block_info->list;
 107 }
 108
 109 /**
 110  * Check, if an ir_node has a scheduling predecessor.
 111  * @param irn The ir node.
 112  * @return 1, if the node has a scheduling predecessor, 0 if not.
 113  */
 114 static inline int _sched_has_prev(const ir_node *irn)
 115 {
 116         const ir_node *block = is_Block(irn) ? irn : get_nodes_block(irn);
 117         const sched_info_t *info = get_irn_sched_info(irn);
 118         const sched_info_t *block_info = get_irn_sched_info(block);
 119         return info->list.prev != &block_info->list;
 120 }
 121
 122 /**
 123  * Get the scheduling successor of a node.
 124  * @param irn The node.
 125  * @return The next ir node in the schedule or the block, if the node has no next node.
 126  */
 127 static inline ir_node *_sched_next(const ir_node *irn)
 128 {
 129         const sched_info_t *info = get_irn_sched_info(irn);
 130         return get_sched_info_irn(get_irn_irg(irn), _sched_entry(info->list.next));
 131 }
 132
 133 /**
 134  * Get the scheduling predecessor of a node.
 135  * @param irn The node.
 136  * @return The next ir node in the schedule or the block, if the node has no predecessor.
 137  * predecessor.
 138  */
 139 static inline ir_node *_sched_prev(const ir_node *irn)
 140 {
 141         const sched_info_t *info = get_irn_sched_info(irn);
 142         return get_sched_info_irn(get_irn_irg(irn), _sched_entry(info->list.prev));
 143 }
 144
 145 /**
 146  * Get the first node in a block schedule.
 147  * @param block The block of which to get the schedule.
 148  * @return The first node in the schedule or the block itself
 149  *         if there is no node in the schedule.
 150  */
 151 static inline ir_node *_sched_first(const ir_node *block)
 152 {
 153         assert(is_Block(block) && "Need a block here");
 154         return _sched_next(block);
 155 }
 156
 157 /**
 158  * Get the last node in a schedule.
 159  * @param  block The block to get the schedule for.
 160  * @return The last ir node in a schedule, or the block itself
 161  *         if there is no node in the schedule.
 162  */
 163 static inline ir_node *_sched_last(const ir_node *block)
 164 {
 165         assert(is_Block(block) && "Need a block here");
 166         return _sched_prev(block);
 167 }
 168
 169 /**
 170  * Reassign the time steps in the schedule.
 171  * @param block The schedule to update.
 172  */
 173 void sched_renumber(const ir_node *block);
 174
 175 static inline void _sched_set_time_stamp(const ir_node *irn)
 176 {
 177         sched_info_t *inf = get_irn_sched_info(irn);
 178         sched_timestep_t before_ts = _sched_entry(inf->list.prev)->time_step;
 179         sched_timestep_t after_ts = _sched_entry(inf->list.next)->time_step;
 180
 181         /*
 182          * If we are the last, we can give us a big time step,
 183          * else we have to compute our time step from our
 184          * neighbours.
 185          */
 186         if(before_ts >= after_ts)
 187                 inf->time_step = before_ts + SCHED_INITIAL_GRANULARITY;
 188         else {
 189                 sched_timestep_t ts = (before_ts + after_ts) / 2;
 190
 191                 /*
 192                  * If the resolution went out, we have to renumber
 193                  * this block.
 194                  */
 195                 if(ts == before_ts || ts == after_ts)
 196                         sched_renumber(get_nodes_block(irn));
 197                 else
 198                         inf->time_step = ts;
 199         }
 200 }
 201
 202 /**
 203  * Add a node to a block schedule.
 204  * @param block The block to whose schedule the node shall be added to.
 205  * @param irn The node to add.
 206  * @return The given node.
 207  */
 208 static inline void _sched_add_before(const ir_node *before, const ir_node *irn)
 209 {
 210         sched_info_t *info = get_irn_sched_info(irn);
 211         assert(_sched_is_scheduled(before));
 212         assert(!_sched_is_scheduled(irn));
 213         assert(!is_Proj(irn));
 214         list_add_tail(&info->list, &get_irn_sched_info(before)->list);
 215         _sched_set_time_stamp(irn);
 216         info->scheduled = 1;
 217 }
 218
 219 /**
 220  * Add a node to a block schedule.
 221  * @param block The block to whose schedule the node shall be added to.
 222  * @param irn The node to add.
 223  * @return The given node.
 224  */
 225 static inline void _sched_add_after(const ir_node *after, const ir_node *irn)
 226 {
 227         sched_info_t *info = get_irn_sched_info(irn);
 228         assert(_sched_is_scheduled(after));
 229         assert(!_sched_is_scheduled(irn));
 230         assert(!is_Proj(irn));
 231         list_add(&info->list, &get_irn_sched_info(after)->list);
 232         _sched_set_time_stamp(irn);
 233         info->scheduled = 1;
 234 }
 235
 236 static inline void _sched_init_block(const ir_node *block)
 237 {
 238         sched_info_t *info = get_irn_sched_info(block);
 239         assert(info->scheduled == 0 && info->time_step == 0);
 240         INIT_LIST_HEAD(&info->list);
 241         info->scheduled = 1;
 242 }
 243
 244 static inline void _sched_reset(const ir_node *node)
 245 {
 246         sched_info_t *info = get_irn_sched_info(node);
 247         info->scheduled = 0;
 248 }
 249
 250 /**
 251  * Remove a node from the scheduled.
 252  * @param irn The node.
 253  */
 254 static inline void _sched_remove(const ir_node *irn)
 255 {
 256         sched_info_t *info = get_irn_sched_info(irn);
 257         list_del(&info->list);
 258         INIT_LIST_HEAD(&info->list);
 259         info->scheduled = 0;
 260 }
 261
 262 /**
 263  * Compare two nodes according to their position in the schedule.
 264  * @param a The first node.
 265  * @param b The second node.
 266  * @return A number smaller, equals to or larger than 0, if a is
 267  *         before, the same, or after b in the schedule.
 268  */
 269 static inline int _sched_cmp(const ir_node *a, const ir_node *b)
 270 {
 271         assert(_sched_is_scheduled(a) && _sched_is_scheduled(b));
 272         assert(get_nodes_block(a) == get_nodes_block(b));
 273
 274         return get_irn_sched_info(a)->time_step - get_irn_sched_info(b)->time_step;
 275 }
 276
 277 /**
 278  * Checks, if one node is scheduled before another.
 279  * @param n1   A node.
 280  * @param n2   Another node.
 281  * @return     1, if n1 is in front of n2 in the schedule, 0 else.
 282  * @note       Both nodes must be in the same block.
 283  */
 284 static inline int _sched_comes_after(const ir_node *n1, const ir_node *n2)
 285 {
 286         assert(_sched_is_scheduled(n1));
 287         assert(_sched_is_scheduled(n2));
 288         assert((is_Block(n1) ? n1 : get_nodes_block(n1)) == (is_Block(n2) ? n2 : get_nodes_block(n2)));
 289         return _sched_get_time_step(n1) < _sched_get_time_step(n2);
 290 }
 291
 292 /**
 293  * A predicate for a node.
 294  * @param irn The node.
 295  * @param data The custom data.
 296  * @return 1 if irn should be skipped. Else 0.
 297  */
 298 typedef int (sched_predicator_t)(const ir_node *irn, void *data);
 299
 300 /**
 301  * Predicate for sched_skip(), returns non-zero if irn is a control flow changing node.
 302  *
 303  * @param irn   the node to evaluate
 304  * @param data  unused
 305  */
 306 int sched_skip_cf_predicator(const ir_node *irn, void *data);
 307
 308 /**
 309  * Predicate for sched_skip(), returns non-zero if irn is a Phi node.
 310  *
 311  * Used with sched_skip().
 312  *
 313  * @param irn  the node to evaluate
 314  * @param data unused
 315  */
 316 int sched_skip_phi_predicator(const ir_node *irn, void *data);
 317
 318 /**
 319  * Skip nodes in a schedule.
 320  * @param from        The node to start from.
 321  * @param forward     The direction (1 for forward, 0 for backward).
 322  * @param predicator  The predicator function which decides what is skipped.
 323  * @param data        context parameter for the predicator.
 324  *
 325  * @return The first node not rejected by the predicator or the block
 326  *         itself if all nodes were rejected.
 327  */
 328 ir_node *sched_skip(ir_node *from, int forward, sched_predicator_t *predicator, void *data);
 329
 330 #define have_sched_info(irg)            _have_sched_info(irg)
 331 #define sched_get_time_step(irn)        _sched_get_time_step(irn)
 332 #define sched_has_next(irn)             _sched_has_next(irn)
 333 #define sched_has_prev(irn)             _sched_has_prev(irn)
 334 #define sched_next(irn)                 _sched_next(irn)
 335 #define sched_prev(irn)                 _sched_prev(irn)
 336 #define sched_first(irn)                _sched_first(irn)
 337 #define sched_last(irn)                 _sched_last(irn)
 338 #define sched_add_before(before, irn)   _sched_add_before(before, irn)
 339 #define sched_add_after(after, irn)     _sched_add_after(after, irn)
 340 #define sched_remove(irn)               _sched_remove(irn)
 341 #define sched_is_scheduled(irn)         _sched_is_scheduled(irn)
 342 #define sched_comes_after(n1, n2)       _sched_comes_after(n1, n2)
 343 #define sched_cmp(a, b)                 _sched_cmp(a, b)
 344
 345 #endif /* FIRM_BE_BESCHED_T_H */