nsz Git - libfirm/blob - ir/be/besched.c

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief       Scheduling utilities for nodes in Blocks and Blocks.
   9  * @author      Sebastian Hack
  10  */
  11 #include "config.h"
  12
  13 #include <stdlib.h>
  14
  15 #include "firm_types.h"
  16 #include "iredges_t.h"
  17 #include "ircons.h"
  18 #include "irgmod.h"
  19 #include "debug.h"
  20
  21 #include "bemodule.h"
  22 #include "bearch.h"
  23 #include "besched.h"
  24 #include "beutil.h"
  25 #include "belistsched.h"
  26 #include "belive.h"
  27
  28 #include "lc_opts.h"
  29 #include "lc_opts_enum.h"
  30 #include "irtools.h"
  31
  32 #define SCHED_INITIAL_GRANULARITY (1 << 14)
  33
  34 static void sched_renumber(ir_node *const block)
  35 {
  36         sched_info_t *inf;
  37         sched_timestep_t step = SCHED_INITIAL_GRANULARITY;
  38
  39         sched_foreach(block, irn) {
  40                 inf = get_irn_sched_info(irn);
  41                 inf->time_step = step;
  42                 step += SCHED_INITIAL_GRANULARITY;
  43         }
  44 }
  45
  46 static inline void sched_set_time_stamp(const ir_node *irn)
  47 {
  48         sched_info_t       *info      = get_irn_sched_info(irn);
  49         const sched_info_t *prev_info = get_irn_sched_info(info->prev);
  50         const sched_info_t *next_info = get_irn_sched_info(info->next);
  51         sched_timestep_t    before_ts = prev_info->time_step;
  52         sched_timestep_t    after_ts  = next_info->time_step;
  53
  54         /*
  55          * If we are the last, we can give us a big time step,
  56          * else we have to compute our time step from our
  57          * neighbours.
  58          */
  59         if(before_ts >= after_ts) {
  60                 info->time_step = before_ts + SCHED_INITIAL_GRANULARITY;
  61                 /* overflow? */
  62                 if (info->time_step <= before_ts) {
  63                         sched_renumber(get_nodes_block(irn));
  64                 }
  65         } else {
  66                 sched_timestep_t ts = (before_ts + after_ts) / 2;
  67
  68                 /*
  69                  * If the resolution went out, we have to renumber
  70                  * this block.
  71                  */
  72                 if(ts == before_ts || ts == after_ts)
  73                         sched_renumber(get_nodes_block(irn));
  74                 else
  75                         info->time_step = ts;
  76         }
  77 }
  78
  79 void sched_add_before(ir_node *before, ir_node *irn)
  80 {
  81         sched_info_t *info      = get_irn_sched_info(irn);
  82         ir_node      *next      = before;
  83         sched_info_t *next_info = get_irn_sched_info(next);
  84         ir_node      *prev      = next_info->prev;
  85         sched_info_t *prev_info = get_irn_sched_info(prev);
  86         assert(sched_is_scheduled(before));
  87         assert(!sched_is_scheduled(irn));
  88         assert(!is_Proj(before));
  89         assert(!is_Proj(irn));
  90
  91         info->prev = prev;
  92         info->next = next;
  93         prev_info->next = irn;
  94         next_info->prev = irn;
  95         sched_set_time_stamp(irn);
  96 }
  97
  98 void sched_add_after(ir_node *after, ir_node *irn)
  99 {
 100         sched_info_t *info      = get_irn_sched_info(irn);
 101         ir_node      *prev      = after;
 102         sched_info_t *prev_info = get_irn_sched_info(prev);
 103         ir_node      *next      = prev_info->next;
 104         sched_info_t *next_info = get_irn_sched_info(next);
 105         assert(sched_is_scheduled(after));
 106         assert(!sched_is_scheduled(irn));
 107         assert(!is_Proj(after));
 108         assert(!is_Proj(irn));
 109
 110         info->prev = prev;
 111         info->next = next;
 112         prev_info->next = irn;
 113         next_info->prev = irn;
 114         sched_set_time_stamp(irn);
 115 }
 116
 117 void sched_remove(ir_node *irn)
 118 {
 119         sched_info_t *info      = get_irn_sched_info(irn);
 120         ir_node      *prev      = info->prev;
 121         ir_node      *next      = info->next;
 122         sched_info_t *prev_info = get_irn_sched_info(prev);
 123         sched_info_t *next_info = get_irn_sched_info(next);
 124         assert(sched_is_scheduled(irn));
 125
 126         prev_info->next = next;
 127         next_info->prev = prev;
 128         info->next      = NULL;
 129         info->prev      = NULL;
 130 }
 131
 132 void sched_replace(ir_node *const old, ir_node *const irn)
 133 {
 134         assert(sched_is_scheduled(old));
 135         assert(!sched_is_scheduled(irn));
 136
 137         sched_info_t *const old_info = get_irn_sched_info(old);
 138         sched_info_t *const irn_info = get_irn_sched_info(irn);
 139         *irn_info = *old_info;
 140
 141         old_info->prev = NULL;
 142         old_info->next = NULL;
 143
 144         ir_node *const prev = irn_info->prev;
 145         ir_node *const next = irn_info->next;
 146         get_irn_sched_info(prev)->next = irn;
 147         get_irn_sched_info(next)->prev = irn;
 148 }
 149
 150 static be_module_list_entry_t *schedulers;
 151 static schedule_func           scheduler;
 152
 153 void be_register_scheduler(const char *name, schedule_func func)
 154 {
 155         if (scheduler == NULL)
 156                 scheduler = func;
 157         be_add_module_to_list(&schedulers, name, (void*)func);
 158 }
 159
 160 void be_schedule_graph(ir_graph *irg)
 161 {
 162         scheduler(irg);
 163 }
 164
 165 BE_REGISTER_MODULE_CONSTRUCTOR(be_init_sched)
 166 void be_init_sched(void)
 167 {
 168         lc_opt_entry_t *be_grp = lc_opt_get_grp(firm_opt_get_root(), "be");
 169         be_add_module_list_opt(be_grp, "scheduler", "scheduling algorithm",
 170                                &schedulers, (void**)&scheduler);
 171 }