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

   1 /*
   2  * Copyright (C) 1995-2007 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       Primitive list scheduling with different node selectors.
  23  * @author      Sebastian Hack
  24  * @date        20.10.2004
  25  * @version     $Id$
  26  */
  27 #ifndef FIRM_BE_BELISTSCHED_H
  28 #define FIRM_BE_BELISTSCHED_H
  29
  30 #include "firm_types.h"
  31 #include "irnodeset.h"
  32
  33 #include "be.h"
  34 #include "bearch.h"
  35 #include "beirg.h"
  36
  37 typedef struct _list_sched_selector_t list_sched_selector_t;
  38
  39 /**
  40  * A selector interface which is used by the list schedule framework.
  41  * You can implement your own list scheduler by implementing these
  42  * functions.
  43  */
  44 struct _list_sched_selector_t {
  45
  46         /**
  47          * Called before a graph is being scheduled.
  48          * @param arch_env The architecture environment.
  49          * @param irg      The graph.
  50          * @return         The environment pointer that is passed to all other functions in this struct.
  51          */
  52         void *(*init_graph)(const list_sched_selector_t *vtab, const arch_env_t *arch_env, ir_graph *irg);
  53
  54         /**
  55          * Called before scheduling starts on a block.
  56          * @param graph_env   The environment.
  57          * @param block       The block which is to be scheduled.
  58          * @return A per-block pointer that is additionally passed to select.
  59          */
  60         void *(*init_block)(void *graph_env, ir_node *block);
  61
  62         /**
  63          * The selection function.
  64          * It picks one node out of the ready list to be scheduled next.
  65          * The function does not have to delete the node from the ready set.
  66          *
  67          * @param block_env   Some private information as returned by init_block().
  68          * @param sched_head  The schedule so far.
  69          * @param ready_set   A set containing all ready nodes. Pick one of these nodes.
  70          * @param live_set    A set containing all nodes currently alive.
  71          * @return The chosen node.
  72          */
  73         ir_node *(*select)(void *block_env, ir_nodeset_t *ready_set,
  74                        ir_nodeset_t *live_set);
  75
  76         /**
  77          * This function decides, if a node should appear in a schedule.
  78          * @param block_env The block environment.
  79          * @param irn       The node.
  80          * @return 1, if the node should be scheduled, 0 if not.
  81          */
  82         int (*to_appear_in_schedule)(void *block_env, const ir_node *irn);
  83
  84         /**
  85          * This function gets executed after a node finally has been made ready.
  86          * @param block_env The block environment.
  87          * @param irn       The node made ready.
  88          * @param pred      The previously scheduled node.
  89          */
  90         void (*node_ready)(void *block_env, ir_node *irn, ir_node *pred);
  91
  92         /**
  93          * This function gets executed after a node finally has been selected.
  94          * @param block_env The block environment.
  95          * @param irn       The selected node.
  96          */
  97         void (*node_selected)(void *block_env, ir_node *irn);
  98
  99         /**
 100          * Returns the execution time of node irn.
 101          */
 102         unsigned (*exectime)(void *block_env, const ir_node *irn);
 103
 104         /**
 105          * Calculates the latency of executing cycle curr_cycle of node curr in cycle pred_cycle
 106          * of node pred.
 107          *
 108          * @param block_env   The block environment.
 109          * @param pred        The previous node.
 110          * @param pred_cycle  The previous node execution cycle.
 111          * @param curr        The current node.
 112          * @param curr_cycle  The current node execution cycle.
 113          */
 114         unsigned (*latency)(void *block_env, const ir_node *pred, int pred_cycle, const ir_node *curr, int curr_cycle);
 115
 116         /**
 117          * Called after a block has been scheduled.
 118          * @param env The environment.
 119          * @param block_env The per block environment as returned by init_block().
 120          */
 121         void (*finish_block)(void *block_env);
 122
 123         /**
 124          * Called after a whole graph has been scheduled.
 125          * @param env The environment.
 126          */
 127         void (*finish_graph)(void *env);
 128
 129 };
 130
 131
 132 /**
 133  * A trivial selector, that just selects the first ready node.
 134  */
 135 extern const list_sched_selector_t *trivial_selector;
 136
 137 extern const list_sched_selector_t *random_selector;
 138
 139 /**
 140  * A selector that tries to minimize the register pressure.
 141  * @note Not really operational yet.
 142  */
 143 extern const list_sched_selector_t *reg_pressure_selector;
 144
 145 /**
 146  * A selector based on trace scheduling as introduced by Muchnik[TM]
 147  */
 148 extern const list_sched_selector_t *muchnik_selector;
 149
 150 /**
 151  * A selector based on trace scheduling as introduced by Muchnik[TM]
 152  * but using the mueller heuristic selector.
 153  */
 154 extern const list_sched_selector_t *heuristic_selector;
 155
 156 /**
 157  * List schedule a graph.
 158  * Each block in the graph gets a list head to its link field being the
 159  * head of the schedule. You can walk this list using the functions in
 160  * list.h.
 161  *
 162  * @param birg    The backend irg.
 163  * @param be_opts The backend options
 164  */
 165 void list_sched(const be_irg_t *birg, be_options_t *be_opts);
 166
 167 /**
 168  * List schedule a block.
 169  * Same as list_sched but only for a certain block (needed for ILP fallback).
 170  */
 171 void list_sched_single_block(const be_irg_t *birg, ir_node *block, be_options_t *be_opts);
 172
 173 #endif /* FIRM_BE_BELISTSCHED_H */