mono/mini/linear-scan.c

   1 /*
   2  * liveness.c: liveness analysis
   3  *
   4  * Author:
   5  *   Dietmar Maurer (dietmar@ximian.com)
   6  *
   7  * (C) 2002 Ximian, Inc.
   8  */
   9
  10 #include "mini.h"
  11
  12 GList *
  13 mono_varlist_insert_sorted (MonoCompile *cfg, GList *list, MonoMethodVar *mv, int sort_type)
  14 {
  15         GList *l;
  16
  17         if (!list)
  18                 return g_list_prepend (NULL, mv);
  19
  20         for (l = list; l; l = l->next) {
  21                 MonoMethodVar *v1 = l->data;
  22
  23                 if (sort_type == 2) {
  24                         if (mv->spill_costs >= v1->spill_costs) {
  25                                 list = g_list_insert_before (list, l, mv);
  26                                 break;
  27                         }
  28                 } else if (sort_type == 1) {
  29                         if (mv->range.last_use.abs_pos <= v1->range.last_use.abs_pos) {
  30                                 list = g_list_insert_before (list, l, mv);
  31                                 break;
  32                         }
  33                 } else {
  34                         if (mv->range.first_use.abs_pos <= v1->range.first_use.abs_pos) {
  35                                 list = g_list_insert_before (list, l, mv);
  36                                 break;
  37                         }
  38                 }
  39         }
  40         if (!l)
  41                 list = g_list_append (list, mv);
  42
  43         return list;
  44 }
  45
  46 //#define DEBUG_LSCAN
  47
  48 void
  49 mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, guint32 *used_mask)
  50 {
  51         GList *l, *a, *active = NULL;
  52         MonoMethodVar *vmv, *amv;
  53         int max_regs, gains [32];
  54         guint32 used_regs = 0;
  55         gboolean cost_driven;
  56
  57         cost_driven = (cfg->comp_done & MONO_COMP_LOOPS);
  58
  59 #ifdef DEBUG_LSCAN
  60         printf ("Linears scan for %s\n", mono_method_full_name (cfg->method, TRUE));
  61 #endif
  62
  63 #ifdef DEBUG_LSCAN
  64         for (l = vars; l; l = l->next) {
  65                 vmv = l->data;
  66                 printf ("VAR %d %08x %08x C%d\n", vmv->idx, vmv->range.first_use.abs_pos,
  67                         vmv->range.last_use.abs_pos, vmv->spill_costs);
  68         }
  69 #endif
  70         max_regs = g_list_length (regs);
  71
  72         for (l = regs; l; l = l->next) {
  73                 int regnum = (int)l->data;
  74                 g_assert (regnum < G_N_ELEMENTS (gains));
  75                 gains [regnum] = 0;
  76         }
  77
  78         /* linear scan */
  79         for (l = vars; l; l = l->next) {
  80                 vmv = l->data;
  81
  82 #ifdef DEBUG_LSCAN
  83                 printf ("START  %2d %08x %08x\n",  vmv->idx, vmv->range.first_use.abs_pos,
  84                         vmv->range.last_use.abs_pos);
  85 #endif
  86                 /* expire old intervals in active */
  87                 while (active) {
  88                         amv = (MonoMethodVar *)active->data;
  89
  90                         if (amv->range.last_use.abs_pos >= vmv->range.first_use.abs_pos)
  91                                 break;
  92
  93 #ifdef DEBUG_LSCAN
  94                         printf ("EXPIR  %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
  95                                 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
  96 #endif
  97                         active = g_list_remove_link (active, active);
  98                         regs = g_list_prepend (regs, (gpointer)amv->reg);
  99                         gains [amv->reg] += amv->spill_costs;
 100                 }
 101
 102                 if (active && g_list_length (active) == max_regs) {
 103                         /* Spill */
 104
 105                         a = g_list_nth (active, max_regs - 1);
 106                         amv = (MonoMethodVar *)a->data;
 107
 108                         if ((cost_driven && amv->spill_costs < vmv->spill_costs) ||
 109                             (!cost_driven && amv->range.last_use.abs_pos > vmv->range.last_use.abs_pos)) {
 110                                 vmv->reg = amv->reg;
 111                                 amv->reg = -1;
 112                                 active = g_list_remove_link (active, a);
 113
 114                                 if (cost_driven)
 115                                         active = mono_varlist_insert_sorted (cfg, active, vmv, 2);
 116                                 else
 117                                         active = mono_varlist_insert_sorted (cfg, active, vmv, 1);
 118
 119 #ifdef DEBUG_LSCAN
 120                                 printf ("SPILL0 %2d %08x %08x C%d\n",  amv->idx,
 121                                         amv->range.first_use.abs_pos, amv->range.last_use.abs_pos,
 122                                         amv->spill_costs);
 123 #endif
 124                         } else {
 125 #ifdef DEBUG_LSCAN
 126                                 printf ("SPILL1 %2d %08x %08x C%d\n",  vmv->idx,
 127                                         vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
 128                                         vmv->spill_costs);
 129 #endif
 130                                 vmv->reg = -1;
 131                         }
 132                 } else {
 133                         /* assign register */
 134
 135                         g_assert (regs);
 136
 137                         vmv->reg = (int)regs->data;
 138
 139                         used_regs |= 1 << vmv->reg;
 140
 141                         regs = g_list_remove_link (regs, regs);
 142
 143 #ifdef DEBUG_LSCAN
 144                         printf ("ADD    %2d %08x %08x C%d\n",  vnum,
 145                                 vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
 146                                 vmv->spill_costs);
 147 #endif
 148                         active = mono_varlist_insert_sorted (cfg, active, vmv, TRUE);
 149                 }
 150
 151
 152 #ifdef DEBUG_LSCAN
 153                 for (a = active; a; a = a->next) {
 154                         amv = (MonoMethodVar *)a->data;
 155                         printf ("ACT    %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
 156                                 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
 157                 }
 158                 printf ("NEXT\n");
 159 #endif
 160         }
 161
 162         for (a = active; a; a = a->next) {
 163                 amv = (MonoMethodVar *)a->data;
 164                 gains [amv->reg] += amv->spill_costs;
 165         }
 166
 167         for (l = vars; l; l = l->next) {
 168                 vmv = l->data;
 169
 170                 if (vmv->reg >= 0)  {
 171                         if (gains [vmv->reg] > 5) {
 172                                 cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
 173                                 cfg->varinfo [vmv->idx]->dreg = vmv->reg;
 174 #ifdef DEBUG_LSCAN
 175                                 printf ("REGVAR %d C%d R%d\n", vmv->idx, vmv->spill_costs, vmv->reg);
 176 #endif
 177                         } else {
 178                                 used_regs &= ~(1 << vmv->reg);
 179                                 vmv->reg = -1;
 180                         }
 181                 }
 182         }
 183
 184         *used_mask |= used_regs;
 185
 186         g_list_free (regs);
 187         g_list_free (active);
 188         g_list_free (vars);
 189 }