view release on metacpan or  search on metacpan

libjit/jit/jit-reg-alloc.c  view on Meta::CPAN

		{
			return reg;
		}
	}
	return -1;
}

/*
 * Check if two values are known to be equal.
 */
static int
are_values_equal(_jit_regdesc_t *desc1, _jit_regdesc_t *desc2)
{
	if(desc1 && desc2 && desc1->value && desc2->value)
	{
		if(desc1->value == desc2->value)
		{
			return 1;
		}
		if(desc1->value->in_register && desc2->value->in_register)
		{
			return desc1->value->reg == desc2->value->reg;
		}
	}
	return 0;
}

/*
 * Exchange the content of two value descriptors.
 */
static void
swap_values(_jit_regdesc_t *desc1, _jit_regdesc_t *desc2)
{
	_jit_regdesc_t tdesc;
	tdesc = *desc1;
	*desc1 = *desc2;
	*desc2 = tdesc;
}

/*
 * Get value usage and liveness information. The accurate liveness data is
 * only available for values used by the current instruction.
 *
 * VALUE_INPUT flag is set if the value is one of the instruction's inputs.
 *
 * VALUE_LIVE and VALUE_USED flags are set for input values only according
 * to the liveness flags provided along with the instruction.
 *
 * VALUE_DEAD flag is set in two cases. First, it is always set for output
 * values. Second, it is set for input values that are neither live nor used.
 *
 * These flags are used when spilling a register. In this case we generally
 * do not know if the values in the register are used by the instruction. If
 * the VALUE_INPUT flag is present then it is so and the value has to be held
 * in the register for the instruction to succeed. If the VALUE_DEAD flag is
 * present then there is no need to spill the value and it may be discarded.
 * Otherwise the value must be spilled.
 *
 * The VALUE_LIVE and VALUE_USED flags may only be set for input values of
 * the instruction. For other values these flags are not set even if they are
 * perfectly alive. These flags are used as a hint for spill cost calculation.
 *
 * NOTE: The output value is considered to be dead because the instruction is
 * just about to recompute it so there is no point to save it.
 *
 * Generally, a value becomes dead just after the instruction that used it
 * last time. The allocator frees dead values after each instruction so it
 * might seem that there is no chance to find any dead value on the current
 * instruction. However if the value is used by the current instruction both
 * as the input and output then it was alive after the last instruction and
 * hence was not freed. And just in case if some dead values may creep through
 * the allocator's checks...
 */
static int
value_usage(_jit_regs_t *regs, jit_value_t value)
{
	int flags;

	flags = 0;
	if(value->is_constant)
	{
		flags |= VALUE_DEAD;
	}
	if(!regs)
	{
		return flags;
	}
	if(value == regs->descs[0].value)
	{
		if(regs->ternary)
		{
			flags |= VALUE_INPUT;
			if(regs->descs[0].used)
			{
				flags |= VALUE_LIVE | VALUE_USED;
			}
			else if(regs->descs[0].live)
			{
				flags |= VALUE_LIVE;
			}
			else
			{
				flags |= VALUE_DEAD;
			}
		}
		else
		{
			flags |= VALUE_DEAD;
		}
	}
	if(value == regs->descs[1].value)
	{
		flags |= VALUE_INPUT;
		if(regs->descs[1].used)
		{
			flags |= VALUE_LIVE | VALUE_USED;
		}
		else if(regs->descs[1].live)
		{
			flags |= VALUE_LIVE;
		}
		else
		{
			flags |= VALUE_DEAD;
		}
	}
	if(value == regs->descs[2].value)
	{
		flags |= VALUE_INPUT;
		if(regs->descs[2].used)
		{
			flags |= VALUE_LIVE | VALUE_USED;
		}
		else if(regs->descs[2].live)
		{
			flags |= VALUE_LIVE;
		}
		else
		{
			flags |= VALUE_DEAD;
		}
	}
	return flags;
}

/*
 * Check if the register contains any live values.
 */
static int
is_register_alive(jit_gencode_t gen, _jit_regs_t *regs, int reg)
{
	int index, usage;

	if(reg < 0)
	{
		return 0;
	}

	/* Assume that a global register is always alive unless it is to be
	   computed right away. */
	if(jit_reg_is_used(gen->permanent, reg))
	{
		if(!regs->ternary
		   && regs->descs[0].value
		   && regs->descs[0].value->has_global_register
		   && regs->descs[0].value->global_reg == reg)
		{
			return 0;
		}
		return 1;
	}

	if(gen->contents[reg].is_long_end)
	{
		reg = get_long_pair_start(reg);
	}
	for(index = 0; index < gen->contents[reg].num_values; index++)
	{
		usage = value_usage(regs, gen->contents[reg].values[index]);
		if((usage & VALUE_DEAD) == 0)
		{
			return 1;
		}
	}

	return 0;
}

#ifdef IS_REGISTER_OCCUPIED
/*
 * Check if the register contains any values either dead or alive
 * that may need to be evicted from it.
 */
static int
is_register_occupied(jit_gencode_t gen, _jit_regs_t *regs, int reg)
{
	if(reg < 0)
	{
		return 0;
	}

	/* Assume that a global register is always occupied. */
	if(jit_reg_is_used(gen->permanent, reg))
	{
		return 1;
	}

	if(gen->contents[reg].is_long_end)
	{
		reg = get_long_pair_start(reg);
	}
	if(gen->contents[reg].num_values)
	{
		return 1;
	}

	return 0;
}
#endif

/*
 * Determine the effect of using a register for a value. This includes the
 * following:
 *  - whether the value is clobbered by the instruction;
 *  - whether the previous contents of the register is clobbered.
 *
 * The value is clobbered by the instruction if it is used as input value
 * and the output value will go to the same register and these two values
 * are not equal. Or the instruction has a side effect that destroys the
 * input value regardless of the output. This is indicated with the
 * CLOBBER_INPUT_VALUE flag.
 *
 * The previous content is clobbered if the register contains any non-dead
 * values that are destroyed by loading the input value, by computing the
 * output value, or as a side effect of the instruction.
 *
 * The previous content is not clobbered if the register contains only dead
 * values or it is used for input value that is already in the register so
 * there is no need to load it and at the same time the instruction has no
 * side effects that destroy the input value or the register is used for
 * output value and the only value it contained before is the same value.
 *
 * The flag CLOBBER_REG indicates if the previous content of the register is
 * clobbered. The flag CLOBBER_OTHER_REG indicates that the other register
 * in a long pair is clobbered.
 *
 */
static int
clobbers_register(jit_gencode_t gen, _jit_regs_t *regs, int index, int reg, int other_reg)
{
	int flags;

	if(!regs->descs[index].value)
	{
		return CLOBBER_NONE;
	}

	if(regs->ternary || !regs->descs[0].value)
	{
		/* this is either a ternary or binary or unary note */
		if(regs->descs[index].clobber)
		{
			flags = CLOBBER_INPUT_VALUE;
		}
#ifdef JIT_REG_STACK
		else if(IS_STACK_REG(reg) && !regs->no_pop)
		{
			flags = CLOBBER_INPUT_VALUE;
		}
#endif
		else
		{
			flags = CLOBBER_NONE;
		}
	}
	else if(index == 0)
	{
		/* this is the output value of a binary or unary op */

		/* special case: a copy operation. Check if we could coalesce
		   the destination value with the source. */
		if(regs->copy
		   && regs->descs[1].value
		   && regs->descs[1].value->in_register
		   && regs->descs[1].value->reg == reg
		   && ((regs->descs[0].value->in_register && regs->descs[0].value->reg == reg)
		       || gen->contents[reg].num_values < JIT_MAX_REG_VALUES
		       || !(regs->descs[1].used || regs->descs[1].live)))
		{
			return CLOBBER_NONE;
		}

		flags = CLOBBER_NONE;
#ifdef IS_REGISTER_OCCUPIED
		if(is_register_occupied(gen, regs, reg))
		{
			flags |= CLOBBER_REG;
		}
		if(is_register_occupied(gen, regs, other_reg))
		{
			flags |= CLOBBER_OTHER_REG;
		}
#else
		if(is_register_alive(gen, regs, reg))
		{
			flags |= CLOBBER_REG;
		}
		if(is_register_alive(gen, regs, other_reg))
		{
			flags |= CLOBBER_OTHER_REG;
		}
#endif
		return flags;
	}
	else if(regs->copy)
	{
		flags = CLOBBER_NONE;
	}
#ifdef JIT_REG_STACK
	else if(IS_STACK_REG(reg) && !regs->no_pop)
	{
		/* this is a binary or unary stack op -- the input value
		   is either popped or overwritten by the output */
		flags = CLOBBER_INPUT_VALUE;
	}
#endif
	else if(reg == regs->descs[0].reg
		|| reg == regs->descs[0].other_reg
		|| other_reg == regs->descs[0].reg)
	{
		/* the input value of a binary or unary op is clobbered
		   by the output value */
		flags = CLOBBER_INPUT_VALUE;
	}
	else if(regs->descs[index].clobber)
	{
		flags = CLOBBER_INPUT_VALUE;
	}
	else
	{
		flags = CLOBBER_NONE;
	}

	if(flags == CLOBBER_NONE)
	{
		if(regs->descs[index].value->has_global_register
		   && regs->descs[index].value->global_reg == reg)
		{
			return CLOBBER_NONE;
		}
		if(regs->descs[index].value->in_register
		   && regs->descs[index].value->reg == reg)
		{
			return CLOBBER_NONE;
		}
	}

#ifdef IS_REGISTER_OCCUPIED
	if(is_register_occupied(gen, regs, reg))
	{
		flags |= CLOBBER_REG;
	}
	if(is_register_occupied(gen, regs, other_reg))
	{
		flags |= CLOBBER_OTHER_REG;
	}
#else
	if(is_register_alive(gen, regs, reg))
	{
		flags |= CLOBBER_REG;
	}
	if(is_register_alive(gen, regs, other_reg))
	{
		flags |= CLOBBER_OTHER_REG;
	}
#endif
	return flags;
}

/*
 * Assign scratch register.
 */
static void
set_scratch_register(jit_gencode_t gen, _jit_regs_t *regs, int index, int reg)
{
	if(reg >= 0)
	{
		regs->scratch[index].reg = reg;

		jit_reg_set_used(gen->touched, reg);
		jit_reg_set_used(regs->clobber, reg);
		jit_reg_set_used(regs->assigned, reg);
	}
}

/*
 * Set value information.
 */
static void
set_regdesc_value(
	_jit_regs_t *regs,
	int index,
	jit_value_t value,
	int flags,
	_jit_regclass_t *regclass,
	int live,
	int used)
{
  	_jit_regdesc_t *desc;

	desc = &regs->descs[index];
	desc->value = value;
	desc->clobber = ((flags & (_JIT_REGS_CLOBBER | _JIT_REGS_EARLY_CLOBBER)) != 0);
	desc->early_clobber = ((flags & _JIT_REGS_EARLY_CLOBBER) != 0);
	desc->regclass = regclass;
	desc->live = live;
	desc->used = used;
}

/*
 * Assign register to a value.
 */
static void
set_regdesc_register(jit_gencode_t gen, _jit_regs_t *regs, int index, int reg, int other_reg)
{
	int assign;
	if(reg >= 0)
	{
		assign = (index > 0 || regs->ternary || regs->descs[0].early_clobber);

		regs->descs[index].reg = reg;
		regs->descs[index].other_reg = other_reg;

		jit_reg_set_used(gen->touched, reg);
		if(assign)
		{
			jit_reg_set_used(regs->assigned, reg);
		}
		if(other_reg >= 0)
		{
			jit_reg_set_used(gen->touched, other_reg);
			if(assign)
			{
				jit_reg_set_used(regs->assigned, other_reg);
			}
		}
	}
}

/*
 * Determine value flags.
 */
static void
set_regdesc_flags(jit_gencode_t gen, _jit_regs_t *regs, int index)
{
  	_jit_regdesc_t *desc;
	int reg, other_reg;
	int clobber, clobber_input;
	int is_input, is_live_input, is_used_input;

#ifdef JIT_REG_DEBUG
	printf("set_regdesc_flags(index = %d)\n", index);
#endif

	desc = &regs->descs[index];
	if(desc->reg < 0 || desc->duplicate)
	{
		return;
	}

	/* See if the value clobbers the register it is assigned to. */
	clobber = clobbers_register(gen, regs, index, desc->reg, desc->other_reg);
#ifdef JIT_REG_DEBUG
	if((clobber & CLOBBER_INPUT_VALUE) != 0)
	{
		printf("clobber input\n");
	}
	if((clobber & CLOBBER_REG) != 0)
	{
		printf("clobber reg\n");
	}
	if((clobber & CLOBBER_OTHER_REG) != 0)
	{
		printf("clobber other reg\n");
	}
#endif

	/* See if this is an input value and whether it is alive. */
	if(regs->ternary)
	{
		is_input = 1;
		is_live_input = desc->live;
		is_used_input = desc->used;
	}
	else if(index > 0)
	{
		is_input = 1;
		if(regs->descs[0].value == desc->value)
		{
			is_live_input = is_used_input = 0;
		}
		else
		{
			is_live_input = desc->live;
			is_used_input = desc->used;
		}
	}
	else
	{
		is_input = is_live_input = is_used_input = 0;
	}

	if(is_input)
	{
		/* Find the register the value is already in (if any). */
		if(desc->value->in_register)
		{
			reg = desc->value->reg;
			if(gen->contents[reg].is_long_start)
			{
				other_reg = jit_reg_other_reg(reg);
			}
			else
			{
				other_reg = -1;
			}
		}
		else
		{
			reg = -1;
			other_reg = -1;
		}

		/* See if the input value is thrashed by other inputs. The allocator
		   tries to avoid thrashing so it may only take place if the register
		   is assigned explicitly. For x87 registers the problem of thrashing
		   may be best solved with fxch but as the stack registers are never
		   assigned explicitely there is no such problem for them at all. */
		if(reg >= 0)
		{
			if(index != 0 && regs->ternary
			   && !are_values_equal(desc, &regs->descs[0]))
			{
				if(reg == regs->descs[0].reg
				   || reg == regs->descs[0].other_reg
				   || (other_reg >= 0
				       && (other_reg == regs->descs[0].reg
					   || other_reg == regs->descs[0].other_reg)))

libjit/jit/jit-reg-alloc.c  view on Meta::CPAN

	}

	if(suitable_reg >= 0)
	{
		set_regdesc_register(gen, regs, index, suitable_reg, suitable_other_reg);
	}
	else
	{
		jit_exception_builtin(JIT_RESULT_COMPILE_ERROR);
	}
}

/*
 * Assign diplicate input value to the same register if possible.
 * The first value has to be already assigned. The second value
 * is assigned to the same register if it is equal to the first
 * and neither of them is clobbered.
 */
static void
check_duplicate_value(_jit_regs_t *regs, _jit_regdesc_t *desc1, _jit_regdesc_t *desc2)
{
	if(desc2->reg < 0 && desc1->reg >= 0 && are_values_equal(desc1, desc2)
#ifdef JIT_REG_STACK
	   && (!IS_STACK_REG(desc1->reg) || regs->x87_arith)
#endif
	   && !desc1->early_clobber && !desc2->early_clobber)
	{
		desc2->reg = desc1->reg;
		desc2->other_reg = desc1->other_reg;
		desc2->duplicate = 1;
	}
}

#ifdef JIT_REG_STACK

/*
 * For x87 instructions choose between pop and no-pop variants.
 */
static void
select_nopop_or_pop(jit_gencode_t gen, _jit_regs_t *regs)
{
	int keep1, keep2;

	if(!regs->x87_arith || !regs->descs[1].value || !regs->descs[2].value)
	{
		return;
	}

	/* Equal values should be assigned to one register and this is
	   going to work only with no-pop instructions. */
	if(are_values_equal(&regs->descs[1], &regs->descs[2]))
	{
		regs->no_pop = 1;
		return;
	}

	/* Determine if we might want to keep input values in registers
	   after the instruction completion. */
	if(regs->descs[1].value->in_register)
	{
		keep1 = is_register_alive(gen, regs, regs->descs[1].value->reg);
	}
	else
	{
		keep1 = (regs->descs[1].used
			 && (regs->descs[1].value != regs->descs[0].value)
			 && !regs->descs[1].clobber);
	}
	if(regs->descs[2].value->in_register)
	{
		keep2 = is_register_alive(gen, regs, regs->descs[2].value->reg);
	}
	else
	{
		keep2 = (regs->descs[2].used
			 && (regs->descs[2].value != regs->descs[0].value)
			 && !regs->descs[2].clobber);
	}

	regs->no_pop = (keep1 || keep2);
}

static void
select_stack_order(jit_gencode_t gen, _jit_regs_t *regs)
{
	_jit_regdesc_t *desc1;
	_jit_regdesc_t *desc2;
	int top_index;

#ifdef JIT_REG_DEBUG
	printf("select_stack_order()\n");
#endif

	if(!regs->x87_arith || regs->wanted_stack_count != 2)
	{
		return;
	}

	desc1 = &regs->descs[1];
	desc2 = &regs->descs[2];

	/* Choose instruction that results into fewer exchanges. If either
	   of two arguments may be on the stack top choose the second to be
	   on top. */
	/* TODO: See if the next instruction wants the output or remaining
	   input to be on the stack top. */
 	if(desc2->copy || desc2->load)
	{
		/* the second argument is going to be on the top */
		top_index = 2;
	}
	else if(desc1->copy || desc1->load)
	{
		/* the first argument is going to be on the top */
		top_index = 1;
	}
	else if(desc2->value->reg == (gen->reg_stack_top - 1))
	{
		/* the second argument is already on the top */
		top_index = 2;
	}
	else if(desc1->value->reg == (gen->reg_stack_top - 1))
	{
		/* the first argument is already on the top */
		top_index = 1;
	}
	else
	{
		top_index = 2;
	}