+static gint
+compare_by_interval_start_pos_func (gconstpointer a, gconstpointer b)
+{
+ MonoMethodVar *v1 = (MonoMethodVar*)a;
+ MonoMethodVar *v2 = (MonoMethodVar*)b;
+
+ if (v1 == v2)
+ return 0;
+ else if (v1->interval->range && v2->interval->range)
+ return v1->interval->range->from - v2->interval->range->from;
+ else if (v1->interval->range)
+ return -1;
+ else
+ return 1;
+}
+
+#if 0
+#define LSCAN_DEBUG(a) do { a; } while (0)
+#else
+#define LSCAN_DEBUG(a)
+#endif
+
+/* FIXME: This is x86 only */
+static inline guint32
+regalloc_cost (MonoCompile *cfg, MonoMethodVar *vmv)
+{
+ MonoInst *ins = cfg->varinfo [vmv->idx];
+
+ /* Load if it is an argument */
+ return (ins->opcode == OP_ARG) ? 1 : 0;
+}
+
+void
+mono_linear_scan2 (MonoCompile *cfg, GList *vars, GList *regs, regmask_t *used_mask)
+{
+ GList *unhandled, *active, *inactive, *l;
+ MonoMethodVar *vmv;
+ gint32 free_pos [sizeof (regmask_t) * 8];
+ gint32 gains [sizeof (regmask_t) * 8];
+ regmask_t used_regs = 0;
+ int n_regs, n_regvars, i;
+
+ for (l = vars; l; l = l->next) {
+ vmv = l->data;
+ LSCAN_DEBUG (printf ("VAR R%d %08x %08x C%d\n", cfg->varinfo [vmv->idx]->dreg, vmv->range.first_use.abs_pos,
+ vmv->range.last_use.abs_pos, vmv->spill_costs));
+ }
+
+ LSCAN_DEBUG (printf ("Linear Scan 2 for %s:\n", mono_method_full_name (cfg->method, TRUE)));
+
+ n_regs = g_list_length (regs);
+ memset (gains, 0, n_regs * sizeof (gint32));
+ unhandled = g_list_sort (g_list_copy (vars), compare_by_interval_start_pos_func);
+ active = NULL;
+ inactive = NULL;
+
+ while (unhandled) {
+ MonoMethodVar *current = unhandled->data;
+ int pos, reg, max_free_pos;
+ gboolean changed;
+
+ unhandled = g_list_delete_link (unhandled, unhandled);
+
+ LSCAN_DEBUG (printf ("Processing R%d: ", cfg->varinfo [current->idx]->dreg));
+ LSCAN_DEBUG (mono_linterval_print (current->interval));
+ LSCAN_DEBUG (printf ("\n"));
+
+ if (!current->interval->range)
+ continue;
+
+ pos = current->interval->range->from;
+
+ /* Check for intervals in active which expired or inactive */
+ changed = TRUE;
+ /* FIXME: Optimize this */
+ while (changed) {
+ changed = FALSE;
+ for (l = active; l != NULL; l = l->next) {
+ MonoMethodVar *v = (MonoMethodVar*)l->data;
+
+ if (v->interval->last_range->to < pos) {
+ active = g_list_delete_link (active, l);
+ LSCAN_DEBUG (printf ("Interval R%d has expired\n", cfg->varinfo [v->idx]->dreg));
+ changed = TRUE;
+ break;
+ }
+ else if (!mono_linterval_covers (v->interval, pos)) {
+ inactive = g_list_append (inactive, v);
+ active = g_list_delete_link (active, l);
+ LSCAN_DEBUG (printf ("Interval R%d became inactive\n", cfg->varinfo [v->idx]->dreg));
+ changed = TRUE;
+ break;
+ }
+ }
+ }
+
+ /* Check for intervals in inactive which expired or active */
+ changed = TRUE;
+ /* FIXME: Optimize this */
+ while (changed) {
+ changed = FALSE;
+ for (l = inactive; l != NULL; l = l->next) {
+ MonoMethodVar *v = (MonoMethodVar*)l->data;
+
+ if (v->interval->last_range->to < pos) {
+ inactive = g_list_delete_link (inactive, l);
+ LSCAN_DEBUG (printf ("\tInterval R%d has expired\n", cfg->varinfo [v->idx]->dreg));
+ changed = TRUE;
+ break;
+ }
+ else if (mono_linterval_covers (v->interval, pos)) {
+ active = g_list_append (active, v);
+ inactive = g_list_delete_link (inactive, l);
+ LSCAN_DEBUG (printf ("\tInterval R%d became active\n", cfg->varinfo [v->idx]->dreg));
+ changed = TRUE;
+ break;
+ }
+ }
+ }
+
+ /* Find a register for the current interval */
+ for (i = 0; i < n_regs; ++i)
+ free_pos [i] = ((gint32)0x7fffffff);
+
+ for (l = active; l != NULL; l = l->next) {
+ MonoMethodVar *v = (MonoMethodVar*)l->data;
+
+ if (v->reg >= 0) {
+ free_pos [v->reg] = 0;
+ LSCAN_DEBUG (printf ("\threg %d is busy (cost %d)\n", v->reg, v->spill_costs));
+ }
+ }
+
+ for (l = inactive; l != NULL; l = l->next) {
+ MonoMethodVar *v = (MonoMethodVar*)l->data;
+ gint32 intersect_pos;
+
+ if (v->reg >= 0) {
+ intersect_pos = mono_linterval_get_intersect_pos (current->interval, v->interval);
+ if (intersect_pos != -1) {
+ free_pos [v->reg] = intersect_pos;
+ LSCAN_DEBUG (printf ("\threg %d becomes free at %d\n", v->reg, intersect_pos));
+ }
+ }
+ }
+
+ max_free_pos = -1;
+ reg = -1;
+ for (i = 0; i < n_regs; ++i)
+ if (free_pos [i] > max_free_pos) {
+ reg = i;
+ max_free_pos = free_pos [i];
+ }
+
+ g_assert (reg != -1);
+
+ if (free_pos [reg] >= current->interval->last_range->to) {
+ /* Register available for whole interval */
+ current->reg = reg;
+ LSCAN_DEBUG (printf ("\tAssigned hreg %d to R%d\n", reg, cfg->varinfo [current->idx]->dreg));
+
+ active = g_list_append (active, current);
+ gains [current->reg] += current->spill_costs;
+ }
+ else {
+ /*
+ * free_pos [reg] > 0 means there is a register available for parts
+ * of the interval, so splitting it is possible. This is not yet
+ * supported, so we spill in this case too.
+ */
+
+ /* Spill an interval */
+
+ /* FIXME: Optimize the selection of the interval */
+
+ if (active) {
+ GList *min_spill_pos;
+#if 0
+ /*
+ * This favors registers with big spill costs, thus larger liveness ranges,
+ * thus actually leading to worse code size.
+ */
+ guint32 min_spill_value = G_MAXINT32;
+
+ for (l = active; l != NULL; l = l->next) {
+ vmv = (MonoMethodVar*)l->data;
+
+ if (vmv->spill_costs < min_spill_value) {
+ min_spill_pos = l;
+ min_spill_value = vmv->spill_costs;
+ }
+ }
+#else
+ /* Spill either the first active or the current interval */
+ min_spill_pos = active;
+#endif
+ vmv = (MonoMethodVar*)min_spill_pos->data;
+ if (vmv->spill_costs < current->spill_costs) {
+ // if (vmv->interval->last_range->to < current->interval->last_range->to) {
+ gains [vmv->reg] -= vmv->spill_costs;
+ vmv->reg = -1;
+ LSCAN_DEBUG (printf ("\tSpilled R%d\n", cfg->varinfo [vmv->idx]->dreg));
+ active = g_list_delete_link (active, min_spill_pos);
+ }
+ else
+ LSCAN_DEBUG (printf ("\tSpilled current (cost %d)\n", current->spill_costs));
+ }
+ else
+ LSCAN_DEBUG (printf ("\tSpilled current\n"));
+ }
+ }
+
+ /* Decrease the gains by the cost of saving+restoring the register */
+ for (i = 0; i < n_regs; ++i) {
+ if (gains [i]) {
+ /* FIXME: This is x86 only */
+ gains [i] -= cfg->method->save_lmf ? 1 : 2;
+ if (gains [i] < 0)
+ gains [i] = 0;
+ }
+ }
+
+ /* Do the actual register assignment */
+ n_regvars = 0;
+ for (l = vars; l; l = l->next) {
+ vmv = l->data;
+
+ if (vmv->reg >= 0) {
+ int reg_index = vmv->reg;
+
+ /* During allocation, vmv->reg is an index into the regs list */
+ vmv->reg = GPOINTER_TO_INT (g_list_nth_data (regs, vmv->reg));
+
+ if ((gains [reg_index] > regalloc_cost (cfg, vmv)) && (cfg->varinfo [vmv->idx]->opcode != OP_REGVAR)) {
+ if (cfg->verbose_level > 2)
+ printf ("REGVAR R%d G%d C%d %s\n", cfg->varinfo [vmv->idx]->dreg, gains [reg_index], regalloc_cost (cfg, vmv), mono_arch_regname (vmv->reg));
+ cfg->varinfo [vmv->idx]->opcode = OP_REGVAR;
+ cfg->varinfo [vmv->idx]->dreg = vmv->reg;
+ n_regvars ++;
+ }
+ else {
+ if (cfg->verbose_level > 2)
+ printf ("COSTLY: %s R%d G%d C%d %s\n", mono_method_full_name (cfg->method, TRUE), cfg->varinfo [vmv->idx]->dreg, gains [reg_index], regalloc_cost (cfg, vmv), mono_arch_regname (vmv->reg));
+ vmv->reg = -1;
+ }
+ }
+ }
+
+ mono_jit_stats.regvars += n_regvars;
+
+ /* Compute used regs */
+ used_regs = 0;
+ for (l = vars; l; l = l->next) {
+ vmv = l->data;
+
+ if (vmv->reg >= 0)
+ used_regs |= 1LL << vmv->reg;
+ }
+
+ *used_mask |= used_regs;
+
+ g_list_free (active);
+ g_list_free (inactive);
+}
+
+#endif /* #ifndef DISABLE_JIT */