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 static gint
  47 compare_by_first_use_func (gconstpointer a, gconstpointer b)
  48 {
  49         MonoMethodVar *v1 = (MonoMethodVar*)a;
  50         MonoMethodVar *v2 = (MonoMethodVar*)b;
  51
  52         return v1->range.first_use.abs_pos - v2->range.first_use.abs_pos;
  53 }
  54
  55 GList *
  56 mono_varlist_sort (MonoCompile *cfg, GList *list, int sort_type)
  57 {
  58         if (sort_type == 0)
  59                 return g_list_sort (list, compare_by_first_use_func);
  60         else
  61                 g_assert_not_reached ();
  62
  63         return NULL;
  64 }
  65
  66 // #define DEBUG_LSCAN
  67
  68 void
  69 mono_linear_scan (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_mask)
  70 {
  71         GList *l, *a, *active = NULL;
  72         MonoMethodVar *vmv, *amv;
  73         int max_regs, gains [sizeof (regmask_t) * 8];
  74         regmask_t used_regs = 0;
  75         gboolean cost_driven;
  76
  77         cost_driven = (cfg->comp_done & MONO_COMP_LOOPS);
  78
  79 #ifdef DEBUG_LSCAN
  80         printf ("Linears scan for %s\n", mono_method_full_name (cfg->method, TRUE));
  81 #endif
  82
  83 #ifdef DEBUG_LSCAN
  84         for (l = vars; l; l = l->next) {
  85                 vmv = l->data;
  86                 printf ("VAR %d %08x %08x C%d\n", vmv->idx, vmv->range.first_use.abs_pos,
  87                         vmv->range.last_use.abs_pos, vmv->spill_costs);
  88         }
  89 #endif
  90         max_regs = g_list_length (regs);
  91
  92         for (l = regs; l; l = l->next) {
  93                 int regnum = (int)l->data;
  94                 g_assert (regnum < G_N_ELEMENTS (gains));
  95                 gains [regnum] = 0;
  96         }
  97
  98         /* linear scan */
  99         for (l = vars; l; l = l->next) {
 100                 vmv = l->data;
 101
 102 #ifdef DEBUG_LSCAN
 103                 printf ("START  %2d %08x %08x\n",  vmv->idx, vmv->range.first_use.abs_pos,
 104                         vmv->range.last_use.abs_pos);
 105 #endif
 106                 /* expire old intervals in active */
 107                 while (active) {
 108                         amv = (MonoMethodVar *)active->data;
 109
 110                         if (amv->range.last_use.abs_pos > vmv->range.first_use.abs_pos)
 111                                 break;
 112
 113 #ifdef DEBUG_LSCAN
 114                         printf ("EXPIR  %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
 115                                 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
 116 #endif
 117                         active = g_list_delete_link (active, active);
 118                         regs = g_list_prepend (regs, (gpointer)amv->reg);
 119                         gains [amv->reg] += amv->spill_costs;
 120                 }
 121
 122                 if (active && g_list_length (active) == max_regs) {
 123                         /* Spill */
 124
 125                         a = g_list_nth (active, max_regs - 1);
 126                         amv = (MonoMethodVar *)a->data;
 127
 128                         if ((cost_driven && amv->spill_costs < vmv->spill_costs) ||
 129                             (!cost_driven && amv->range.last_use.abs_pos > vmv->range.last_use.abs_pos)) {
 130                                 vmv->reg = amv->reg;
 131                                 amv->reg = -1;
 132                                 active = g_list_delete_link (active, a);
 133
 134                                 if (cost_driven)
 135                                         active = mono_varlist_insert_sorted (cfg, active, vmv, 2);
 136                                 else
 137                                         active = mono_varlist_insert_sorted (cfg, active, vmv, 1);
 138
 139 #ifdef DEBUG_LSCAN
 140                                 printf ("SPILL0 %2d %08x %08x C%d\n",  amv->idx,
 141                                         amv->range.first_use.abs_pos, amv->range.last_use.abs_pos,
 142                                         amv->spill_costs);
 143 #endif
 144                         } else {
 145 #ifdef DEBUG_LSCAN
 146                                 printf ("SPILL1 %2d %08x %08x C%d\n",  vmv->idx,
 147                                         vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
 148                                         vmv->spill_costs);
 149 #endif
 150                                 vmv->reg = -1;
 151                         }
 152                 } else {
 153                         /* assign register */
 154
 155                         g_assert (regs);
 156
 157                         vmv->reg = (int)regs->data;
 158
 159                         used_regs |= 1LL << vmv->reg;
 160
 161                         regs = g_list_delete_link (regs, regs);
 162
 163 #ifdef DEBUG_LSCAN
 164                         printf ("ADD    %2d %08x %08x C%d R%d\n",  vmv->idx,
 165                                 vmv->range.first_use.abs_pos, vmv->range.last_use.abs_pos,
 166                                 vmv->spill_costs, vmv->reg);
 167 #endif
 168                         active = mono_varlist_insert_sorted (cfg, active, vmv, TRUE);
 169                 }
 170
 171
 172 #ifdef DEBUG_LSCAN
 173                 for (a = active; a; a = a->next) {
 174                         amv = (MonoMethodVar *)a->data;
 175                         printf ("ACT    %2d %08x %08x C%d R%d\n", amv->idx, amv->range.first_use.abs_pos,
 176                                 amv->range.last_use.abs_pos, amv->spill_costs, amv->reg);
 177                 }
 178                 printf ("NEXT\n");
 179 #endif
 180         }
 181
 182         for (a = active; a; a = a->next) {
 183                 amv = (MonoMethodVar *)a->data;
 184                 gains [amv->reg] += amv->spill_costs;
 185         }
 186
 187         for (l = vars; l; l = l->next) {
 188                 vmv = l->data;
 189
 190                 if (vmv->reg >= 0)  {
 191                         if ((gains [vmv->reg] > mono_arch_regalloc_cost (cfg, vmv)) && (cfg->varinfo [vmv->idx]->opcode != OP_REGVAR)) {
 192                                 cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
 193                                 cfg->varinfo [vmv->idx]->dreg = vmv->reg;
 194                                 if (cfg->verbose_level > 2)
 195                                         printf ("REGVAR %d C%d R%d\n", vmv->idx, vmv->spill_costs, vmv->reg);
 196                         } else
 197                                 vmv->reg = -1;
 198                 }
 199         }
 200
 201         /* Compute used regs */
 202         used_regs = 0;
 203         for (l = vars; l; l = l->next) {
 204                 vmv = l->data;
 205
 206                 if (vmv->reg >= 0)
 207                         used_regs |= 1LL << vmv->reg;
 208         }
 209
 210         *used_mask |= used_regs;
 211
 212 #ifdef DEBUG_LSCAN
 213         if (cfg->verbose_level > 2)
 214                 printf ("EXIT: final used mask: %08x\n", *used_mask);
 215 #endif
 216
 217         g_list_free (regs);
 218         g_list_free (active);
 219         g_list_free (vars);
 220 }
 221