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