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

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