nsz Git - libfirm/blob - ir/be/mips/mips_scheduler.c

   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   Mips implementation of list scheduler selector
  23  * @author  Matthias Braun, Mehdi
  24  * @version $Id$
  25  */
  26 #include "config.h"
  27
  28 #include "mips_scheduler.h"
  29
  30 #include "../besched.h"
  31 #include "be.h"
  32 #include "../beabi.h"
  33 #include "../belistsched.h"
  34 #include "iredges.h"
  35 #include "ircons.h"
  36 #include "gen_mips_regalloc_if.h"
  37
  38 #include "mips_new_nodes.h"
  39
  40 list_sched_selector_t mips_sched_selector;
  41
  42 typedef struct {
  43         pset *div_set;
  44         /**
  45          * This array holds an entry for each register that specifies how much cycles
  46          * have to pass before we can access that register again
  47          * (because mips will write the register value back in the WB phase of the pipeline)
  48          */
  49         int busy_registers[N_mips_gp_REGS];
  50         /// current block
  51         ir_node* block;
  52         ir_node* last_nop;
  53 } mips_sched_env_t;
  54
  55 /* Matze: deprecated and totally broken */
  56 #if 0
  57
  58 static void *mips_scheduler_init_graph(const list_sched_selector_t *vtab, ir_graph *irg)
  59 {
  60         mips_sched_env_t *sched_env = XMALLOCZ(mips_sched_env_t);
  61
  62         sched_env->div_set = new_pset(pset_default_ptr_cmp, 4);
  63
  64         return sched_env;
  65 }
  66
  67 static void mips_scheduler_finish_graph(void* graph_env)
  68 {
  69         mips_sched_env_t *sched_env = (mips_sched_env_t*) graph_env;
  70         del_pset(sched_env->div_set);
  71 }
  72
  73 static void *mips_scheduler_init_block(void *graph_env, ir_node *block)
  74 {
  75         mips_sched_env_t *sched_env = (mips_sched_env_t*) graph_env;
  76         assert(pset_count(sched_env->div_set) == 0);
  77         srand(12234);
  78         // TODO later we might have blocks that don't end in a jump
  79         memset(&sched_env->busy_registers, 0, sizeof(sched_env->busy_registers));
  80         sched_env->block = block;
  81         sched_env->last_nop = NULL;
  82         return sched_env;
  83 }
  84
  85 static void mips_scheduler_finish_block(void* graph_env)
  86 {
  87         mips_sched_env_t *sched_env = (mips_sched_env_t*) graph_env;
  88         // attach last nop to end node (so that firm doesn't discard it)
  89         if (sched_env->last_nop != NULL) {
  90                 ir_node* end = get_irg_end(get_irn_irg(sched_env->block));
  91                 (void) end;
  92                 // TODO
  93         }
  94         sched_env->block = NULL;
  95 }
  96
  97 static int mips_scheduler_to_appear_in_schedule(void *block_env, const ir_node *irn)
  98 {
  99         return is_mips_irn(irn) && !is_mips_zero(irn) && !is_mips_reinterpret_conv(irn) && !is_mips_fallthrough(irn);
 100 }
 101
 102 static void mips_collect_mflohis(pset* set, ir_node* node)
 103 {
 104         // construct a list of nodes that need to be scheduled before
 105         // we are allowed to schedule another div or mul instruction
 106         const ir_edge_t *edge, *edge2;
 107
 108         if (is_mips_div(node)) {
 109                 foreach_out_edge(node, edge) {
 110                         const ir_node* node2 = get_edge_src_irn(edge);
 111
 112                         assert(is_Proj(node2));
 113                         foreach_out_edge(node2, edge2) {
 114                                 const ir_node* node3 = get_edge_src_irn(edge2);
 115                                 if (is_mips_mfhi(node3) || is_mips_mflo(node3))
 116                                         pset_insert_ptr(set, node3);
 117                         }
 118                 }
 119         } else if (is_mips_mult(node)) {
 120                 foreach_out_edge(node, edge) {
 121                         const ir_node* node2 = get_edge_src_irn(edge);
 122
 123                         if (is_mips_mfhi(node2) || is_mips_mflo(node2))
 124                                 pset_insert_ptr(set, node2);
 125                 }
 126         }
 127 }
 128
 129 static int mips_scheduler_node_allowed(mips_sched_env_t *sched_env, ir_node* node)
 130 {
 131         if (pset_count(sched_env->div_set) != 0 && (is_mips_div(node) || is_mips_mult(node))) {
 132                 return 0;
 133         }
 134
 135         return 1;
 136 }
 137
 138 static ir_node *mips_scheduler_select(void *block_env, nodeset *ready_set, nodeset *live_set)
 139 {
 140         mips_sched_env_t *sched_env = (mips_sched_env_t*) block_env;
 141         ir_node *node = NULL;
 142         ir_node *block = sched_env->block;
 143         ir_node *condjmp = NULL;
 144         ir_graph *irg = get_irn_irg(block);
 145         int have_non_branch_nodes = 0;
 146
 147         // test all nodes in the ready set and take the first non-branch that
 148         // is allowed
 149         for (node = nodeset_first(ready_set); node != NULL; node = nodeset_next(ready_set)) {
 150                 if (arch_irn_class_is(node, branch)) {
 151                         if (is_irn_forking(node))
 152                                 condjmp = node;
 153                         continue;
 154                 }
 155
 156                 have_non_branch_nodes = 1;
 157
 158                 if (mips_scheduler_node_allowed(sched_env, node))
 159                 {
 160                         nodeset_break(ready_set);
 161
 162                         // TODO update busy_registers
 163
 164                         if (is_mips_div(node) || is_mips_mult(node)) {
 165                                 mips_collect_mflohis(sched_env->div_set, node);
 166                         } else if (is_mips_mflo(node) || is_mips_mfhi(node)) {
 167                                 pset_remove_ptr(sched_env->div_set, node);
 168                         }
 169
 170                         return node;
 171                 }
 172         }
 173
 174         // if we arrive here no non-branch node was found that we can emit
 175
 176         // return a branch if there are just branches left
 177         if (!have_non_branch_nodes) {
 178                 // schedule conditional branches before non-conditional ones
 179                 if (condjmp != NULL) {
 180                         return condjmp;
 181                 }
 182                 node = nodeset_first(ready_set);
 183                 assert(arch_irn_class_is(node, branch));
 184                 nodeset_break(ready_set);
 185                 return node;
 186         }
 187
 188         // emit a nop
 189         node = new_rd_mips_nop(NULL, irg, block, mode_M);
 190         keep_alive(node);
 191         return node;
 192 }
 193
 194 #endif
 195
 196 static int mips_to_appear_in_schedule(void *block_env, const ir_node *node)
 197 {
 198         (void) block_env;
 199
 200         if (!is_mips_irn(node))
 201                 return -1;
 202         if (is_mips_zero(node) || is_mips_Immediate(node))
 203                 return 0;
 204
 205         return 1;
 206 }
 207
 208 list_sched_selector_t  mips_selector;
 209
 210 /**
 211  * Returns the reg_pressure scheduler with to_appear_in_schedule() overloaded
 212  */
 213 const list_sched_selector_t *mips_get_list_sched_selector(const void *self,
 214                 list_sched_selector_t *selector)
 215 {
 216         (void) self;
 217 #if 0
 218         memset(&mips_sched_selector, 0, sizeof(mips_sched_selector));
 219         mips_sched_selector.init_graph = mips_scheduler_init_graph;
 220         mips_sched_selector.init_block = mips_scheduler_init_block;
 221         mips_sched_selector.select = mips_scheduler_select;
 222         mips_sched_selector.to_appear_in_schedule = mips_scheduler_to_appear_in_schedule;
 223         mips_sched_selector.finish_block = mips_scheduler_finish_block;
 224         mips_sched_selector.finish_graph = mips_scheduler_finish_graph;
 225         //return &mips_sched_selector;
 226 #endif
 227         memcpy(&mips_selector, selector, sizeof(mips_selector));
 228         mips_selector.to_appear_in_schedule = mips_to_appear_in_schedule;
 229
 230         return &mips_selector;
 231 }
 232
 233 const ilp_sched_selector_t *mips_get_ilp_sched_selector(const void *self)
 234 {
 235         (void) self;
 236         return NULL;
 237 }