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

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