storage.c

/*
 * Storage - associate pseudos with "storage" that keeps them alive
 * between basic blocks.  The aim is to be able to turn as much of
 * the global storage allocation problem as possible into a local
 * per-basic-block one.
 *
 * Copyright (C) 2004 Linus Torvalds
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "symbol.h"
#include "expression.h"
#include "linearize.h"
#include "storage.h"

ALLOCATOR(storage, "storages");
ALLOCATOR(storage_hash, "storage hash");

#define MAX_STORAGE_HASH 64
static struct storage_hash_list *storage_hash_table[MAX_STORAGE_HASH];

static inline unsigned int storage_hash(struct basic_block *bb, pseudo_t pseudo, enum inout_enum inout)
{
	unsigned hash = hashval(bb) + hashval(pseudo) + hashval(inout);
	hash += hash / MAX_STORAGE_HASH;
	return hash & (MAX_STORAGE_HASH-1);
}

static int hash_list_cmp(const void *_a, const void *_b)
{
	const struct storage_hash *a = _a;
	const struct storage_hash *b = _b;
	if (a->pseudo != b->pseudo)
		return a->pseudo < b->pseudo ? -1 : 1;
	return 0;
}

static void sort_hash_list(struct storage_hash_list **listp)
{
	sort_list((struct ptr_list **)listp, hash_list_cmp);
}

struct storage_hash_list *gather_storage(struct basic_block *bb, enum inout_enum inout)
{
	int i;
	struct storage_hash *entry, *prev;
	struct storage_hash_list *list = NULL;

	for (i = 0; i < MAX_STORAGE_HASH; i++) {
		struct storage_hash *hash;
		FOR_EACH_PTR(storage_hash_table[i], hash) {
			if (hash->bb == bb && hash->inout == inout)
				add_ptr_list(&list, hash);
		} END_FOR_EACH_PTR(hash);
	}
	sort_hash_list(&list);

	prev = NULL;
	FOR_EACH_PTR(list, entry) {
		if (prev && entry->pseudo == prev->pseudo) {
			assert(entry == prev);
			DELETE_CURRENT_PTR(entry);
		}
		prev = entry;
	} END_FOR_EACH_PTR(entry);
	PACK_PTR_LIST(&list);
	return list;
}

static void name_storage(void)
{
	int i;
	int name = 0;

	for (i = 0; i < MAX_STORAGE_HASH; i++) {
		struct storage_hash *hash;
		FOR_EACH_PTR(storage_hash_table[i], hash) {
			struct storage *storage = hash->storage;
			if (storage->name)
				continue;
			storage->name = ++name;
		} END_FOR_EACH_PTR(hash);
	}
}

struct storage *lookup_storage(struct basic_block *bb, pseudo_t pseudo, enum inout_enum inout)
{
	struct storage_hash_list *list = storage_hash_table[storage_hash(bb,pseudo,inout)];
	struct storage_hash *hash;

	FOR_EACH_PTR(list, hash) {
		if (hash->bb == bb && hash->pseudo == pseudo && hash->inout == inout)
			return hash->storage;
	} END_FOR_EACH_PTR(hash);
	return NULL;
}

void add_storage(struct storage *storage, struct basic_block *bb, pseudo_t pseudo, enum inout_enum inout)
{
	struct storage_hash_list **listp = storage_hash_table + storage_hash(bb,pseudo,inout);
	struct storage_hash *hash = alloc_storage_hash(storage);

	hash->bb = bb;
	hash->pseudo = pseudo;
	hash->inout = inout;

	add_ptr_list(listp, hash);
}


static int storage_hash_cmp(const void *_a, const void *_b)
{
	const struct storage_hash *a = _a;
	const struct storage_hash *b = _b;
	struct storage *aa = a->storage;
	struct storage *bb = b->storage;

	if (a->bb != b->bb)
		return a->bb < b->bb ? -1 : 1;
	if (a->inout != b->inout)
		return a->inout < b->inout ? -1 : 1;
	if (aa->type != bb->type)
		return aa->type < bb->type ? -1 : 1;
	if (aa->regno != bb->regno)
		return aa->regno < bb->regno ? -1 : 1;
	return 0;
}

static void vrfy_storage(struct storage_hash_list **listp)
{
	struct storage_hash *entry, *last;

	sort_list((struct ptr_list **)listp, storage_hash_cmp);
	last = NULL;
	FOR_EACH_PTR(*listp, entry) {
		if (last) {
			struct storage *a = last->storage;
			struct storage *b = entry->storage;
			if (a == b)
				continue;
			if (last->bb == entry->bb
			    && last->inout == entry->inout
			    && a->type != REG_UDEF
			    && a->type == b->type
			    && a->regno == b->regno) {
				printf("\t BAD: same storage as %s in %p: %s (%s and %s)\n",
					last->inout == STOR_IN ? "input" : "output",
					last->bb,
					show_storage(a),
					show_pseudo(last->pseudo),
					show_pseudo(entry->pseudo));
			}
		}
		last = entry;
	} END_FOR_EACH_PTR(entry);
}

void free_storage(void)
{
	int i;

	for (i = 0; i < MAX_STORAGE_HASH; i++) {
		vrfy_storage(storage_hash_table + i);
		free_ptr_list(storage_hash_table + i);
	}
}

const char *show_storage(struct storage *s)
{
	static char buffer[1024];
	if (!s)
		return "none";
	switch (s->type) {
	case REG_REG:
		sprintf(buffer, "reg%d (%d)", s->regno, s->name);
		break;
	case REG_STACK:
		sprintf(buffer, "%d(SP) (%d)", s->offset, s->name);
		break;
	case REG_ARG:
		sprintf(buffer, "ARG%d (%d)", s->regno, s->name);
		break;
	default:
		sprintf(buffer, "%d:%d (%d)", s->type, s->regno, s->name);
		break;
	}
	return buffer;
}

/*
 * Combine two storage allocations into one.
 *
 * We just randomly pick one over the other, and replace
 * the other uses.
 */
static struct storage * combine_storage(struct storage *src, struct storage *dst)
{
	struct storage **usep;

	/* Remove uses of "src_storage", replace with "dst" */
	FOR_EACH_PTR(src->users, usep) {
		assert(*usep == src);
		*usep = dst;
		add_ptr_list(&dst->users, usep);
	} END_FOR_EACH_PTR(usep);

	/* Mark it unused */
	src->type = REG_BAD;
	src->users = NULL;
	return dst;
}

static void set_up_bb_storage(struct basic_block *bb)
{
	struct basic_block *child;

	FOR_EACH_PTR(bb->children, child) {
		pseudo_t pseudo;
		FOR_EACH_PTR(child->needs, pseudo) {
			struct storage *child_in, *parent_out;

			parent_out = lookup_storage(bb, pseudo, STOR_OUT);
			child_in = lookup_storage(child, pseudo, STOR_IN);

			if (parent_out) {
				if (!child_in) {
					add_storage(parent_out, child, pseudo, STOR_IN);
					continue;
				}
				if (parent_out == child_in)
					continue;
				combine_storage(parent_out, child_in);
				continue;
			}
			if (child_in) {
				add_storage(child_in, bb, pseudo, STOR_OUT);
				continue;
			}
			parent_out = alloc_storage();
			add_storage(parent_out, bb, pseudo, STOR_OUT);
			add_storage(parent_out, child, pseudo, STOR_IN);
		} END_FOR_EACH_PTR(pseudo);
	} END_FOR_EACH_PTR(child);
}

static void set_up_argument_storage(struct entrypoint *ep, struct basic_block *bb)
{
	pseudo_t arg;

	FOR_EACH_PTR(bb->needs, arg) {
		struct storage *storage = alloc_storage();

		/* FIXME! Totally made-up argument passing conventions */
		if (arg->type == PSEUDO_ARG) {
			storage->type = REG_ARG;
			storage->regno = arg->nr;
		}
		add_storage(storage, bb, arg, STOR_IN);
	} END_FOR_EACH_PTR(arg);
}

/*
 * One phi-source may feed multiple phi nodes. If so, combine
 * the storage output for this bb into one entry to reduce
 * storage pressure.
 */
static void combine_phi_storage(struct basic_block *bb)
{
	struct instruction *insn;
	FOR_EACH_PTR(bb->insns, insn) {
		struct instruction *phi;
		struct storage *last;

		if (!insn->bb || insn->opcode != OP_PHISOURCE)
			continue;
		last = NULL;
		FOR_EACH_PTR(insn->phi_users, phi) {
			struct storage *storage = lookup_storage(bb, phi->target, STOR_OUT);
			if (!storage) {
				DELETE_CURRENT_PTR(phi);
				continue;
			}
			if (last && storage != last)
				storage = combine_storage(storage, last);
			last = storage;
		} END_FOR_EACH_PTR(phi);
		PACK_PTR_LIST(&insn->phi_users);
	} END_FOR_EACH_PTR(insn);
}

void set_up_storage(struct entrypoint *ep)
{
	struct basic_block *bb;

	/* First set up storage for the incoming arguments */
	set_up_argument_storage(ep, ep->entry->bb);

	/* Then do a list of all the inter-bb storage */
	FOR_EACH_PTR(ep->bbs, bb) {
		set_up_bb_storage(bb);
		combine_phi_storage(bb);
	} END_FOR_EACH_PTR(bb);

	name_storage();
}