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

   1 /**
   2  * Trivial node selector.
   3  * @author Matthias Braun
   4  * @date   29.08.2006
   5  * @cvs-id $Id$
   6  */
   7 #ifdef HAVE_CONFIG_H
   8 #include "config.h"
   9 #endif
  10
  11 #include <stdlib.h>
  12
  13 #include "besched_t.h"
  14 #include "belistsched.h"
  15
  16 /**
  17  * The random selector:
  18  * Just assure that branches are executed last, otherwise select a random node
  19  */
  20 static ir_node *random_select(void *block_env, nodeset *ready_set, nodeset *live_set)
  21 {
  22         const arch_env_t *arch_env = block_env;
  23         ir_node          *irn      = NULL;
  24         int only_branches_left = 1;
  25
  26         /* assure that branches and constants are executed last */
  27         for (irn = nodeset_first(ready_set); irn; irn = nodeset_next(ready_set)) {
  28                 if (! arch_irn_class_is(arch_env, irn, branch)) {
  29                         only_branches_left = 0;
  30                         nodeset_break(ready_set);
  31                         break;
  32                 }
  33         }
  34
  35         if(only_branches_left) {
  36                 /* at last: schedule branches */
  37                 irn = nodeset_first(ready_set);
  38                 nodeset_break(ready_set);
  39         } else {
  40                 do {
  41                         // take 1 random node
  42                         int n = rand() % pset_count(ready_set);
  43                         int i = 0;
  44                         for(irn = nodeset_first(ready_set); irn; irn = nodeset_next(ready_set)) {
  45                                 if(i == n) {
  46                                         nodeset_break(ready_set);
  47                                         break;
  48                                 }
  49                                 ++i;
  50                         }
  51                 } while(arch_irn_class_is(arch_env, irn, branch));
  52         }
  53
  54         return irn;
  55 }
  56
  57 static void *random_init_graph(const list_sched_selector_t *vtab, const arch_env_t *arch_env, ir_graph *irg)
  58 {
  59         /* Using time(NULL) as a seed here gives really random results,
  60            but is NOT deterministic which makes debugging impossible.
  61            Moreover no-one want non-deterministic compilers ... */
  62         srand(0x4711);
  63         return (void *)arch_env;
  64 }
  65
  66 static void *random_init_block(void *graph_env, ir_node *bl)
  67 {
  68         return graph_env;
  69 }
  70
  71 static const list_sched_selector_t random_selector_struct = {
  72         random_init_graph,
  73         random_init_block,
  74         random_select,
  75         NULL,                /* to_appear_in_schedule */
  76         NULL,                /* node_ready */
  77         NULL,                /* node_selected */
  78         NULL,                /* exectime */
  79         NULL,                /* latency */
  80         NULL,                /* finish_block */
  81         NULL                 /* finish_graph */
  82 };
  83
  84 const list_sched_selector_t *random_selector = &random_selector_struct;