<commit_before>#include <jive/regalloc/color.h>

#include <jive/regalloc/assignment-tracker-private.h>
#include <jive/regalloc/shaped-graph.h>
#include <jive/regalloc/shaped-variable-private.h>

static jive_shaped_variable *
find_next_uncolored(const jive_var_assignment_tracker * tracker)
{
	if (tracker->pressured_max) {
		JIVE_DEBUG_ASSERT(tracker->pressured[tracker->pressured_max - 1].first);
		return tracker->pressured[tracker->pressured_max - 1].first;
	} else if (tracker->trivial.first) {
		return tracker->trivial.first;
	} else return NULL;
}

void
jive_regalloc_color(jive_shaped_graph * shaped_graph)
{
	for(;;) {
		jive_shaped_variable * shaped_variable = find_next_uncolored(&shaped_graph->var_assignment_tracker);
		if (!shaped_variable)
			break;
		
		JIVE_DEBUG_ASSERT(!jive_variable_get_resource_name(shaped_variable->variable));
		
		const jive_resource_name * name = 0;
		struct jive_allowed_resource_names_hash_iterator i;
		JIVE_HASH_ITERATE(jive_allowed_resource_names_hash, shaped_variable->allowed_names, i) {
			name = i.entry->name;
			break;
		}<commit_msg>regalloc: minimize pressure while coloring<commit_after>#include <jive/regalloc/color.h>

#include <jive/regalloc/assignment-tracker-private.h>
#include <jive/regalloc/shaped-graph.h>
#include <jive/regalloc/shaped-variable-private.h>

static jive_shaped_variable *
find_next_uncolored(const jive_var_assignment_tracker * tracker)
{
	if (tracker->pressured_max) {
		JIVE_DEBUG_ASSERT(tracker->pressured[tracker->pressured_max - 1].first);
		return tracker->pressured[tracker->pressured_max - 1].first;
	} else if (tracker->trivial.first) {
		return tracker->trivial.first;
	} else return NULL;
}

static const jive_resource_name *
find_allowed_name(jive_context * context, jive_shaped_variable * candidate)
{
	jive_variable * variable = candidate->variable;
	
	/* of the allowed registers, choose the one that puts the
	smallest amount of "pressure" on interfering variables */
	
	jive_resource_class_count cross_count;
	jive_resource_class_count_init(&cross_count, context);
	
	const jive_resource_class * rescls = jive_variable_get_resource_class(variable);
	
	const jive_resource_name * best_name = 0;
	size_t best_pressure = candidate->interference.nitems + 1;
	
	struct jive_allowed_resource_names_hash_iterator i;
	JIVE_HASH_ITERATE(jive_allowed_resource_names_hash, candidate->allowed_names, i) {
		const jive_resource_name * name = i.entry->name;
		size_t pressure = 0;
		
		const jive_resource_class * overflow;
		overflow = jive_resource_class_count_check_change(&cross_count, rescls, name->resource_class);
		if (overflow)
			continue;
		
		struct jive_variable_interference_hash_iterator j;
		JIVE_HASH_ITERATE(jive_variable_interference_hash, candidate->interference, j) {
			jive_shaped_variable * other = j.entry->shaped_variable;
			if (jive_allowed_resource_names_contains(&other->allowed_names, name)) {
				/* choosing this register would reduce the number
				of choices for another variable */
				pressure  = pressure + 1;
			}
		}
		
		if (pressure < best_pressure) {
			best_name = name;
			best_pressure = pressure;
		}
	}
	
	jive_resource_class_count_fini(&cross_count);
	
	return best_name;
}

void
jive_regalloc_color(jive_shaped_graph * shaped_graph)
{
	for(;;) {
		jive_shaped_variable * shaped_variable = find_next_uncolored(&shaped_graph->var_assignment_tracker);
		if (!shaped_variable)
			break;
		
		JIVE_DEBUG_ASSERT(!jive_variable_get_resource_name(shaped_variable->variable));
		
		const jive_resource_name * name = find_allowed_name(shaped_graph->context, shaped_variable);
{'fraction_non_alphanumeric': 0.09836065573770492, 'fraction_numerical': 0.0025006946373992774, 'mean_word_length': 5.936416184971098, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 40, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '728578', 'n_tokens_mistral': 1321, 'n_tokens_neox': 1200, 'n_words': 203}