r600g: Initial import

1 files changed, 446 insertions, 0 deletions

diff --git a/src/gallium/drivers/r600/r600_compiler.c b/src/gallium/drivers/r600/r600_compiler.c
new file mode 100644
index 00000000000..f1be2bbdf4f
--- /dev/null
+++ b/src/gallium/drivers/r600/r600_compiler.c
@@ -0,0 +1,446 @@
+/*
+ * Copyright 2010 Jerome Glisse <[email protected]>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * on the rights to use, copy, modify, merge, publish, distribute, sub
+ * license, and/or sell copies of the Software, and to permit persons to whom
+ * the Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHOR(S) AND/OR THEIR SUPPLIERS BE LIABLE FOR ANY CLAIM,
+ * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
+ * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
+ * USE OR OTHER DEALINGS IN THE SOFTWARE.
+ */
+#include <stdlib.h>
+#include <string.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <errno.h>
+#include "r600_compiler.h"
+
+struct c_vector *c_vector_new(void)
+{
+	struct c_vector *v = calloc(1, sizeof(struct c_vector));
+
+	if (v == NULL) {
+		return NULL;
+	}
+	c_list_init(v);
+	return v;
+}
+
+static unsigned c_opcode_is_alu(unsigned opcode)
+{
+	switch (opcode) {
+	case C_OPCODE_MOV:
+	case C_OPCODE_MUL:
+	case C_OPCODE_MAD:
+	case C_OPCODE_ARL:
+	case C_OPCODE_LIT:
+	case C_OPCODE_RCP:
+	case C_OPCODE_RSQ:
+	case C_OPCODE_EXP:
+	case C_OPCODE_LOG:
+	case C_OPCODE_ADD:
+	case C_OPCODE_DP3:
+	case C_OPCODE_DP4:
+	case C_OPCODE_DST:
+	case C_OPCODE_MIN:
+	case C_OPCODE_MAX:
+	case C_OPCODE_SLT:
+	case C_OPCODE_SGE:
+	case C_OPCODE_SUB:
+	case C_OPCODE_LRP:
+	case C_OPCODE_CND:
+	case C_OPCODE_DP2A:
+	case C_OPCODE_FRC:
+	case C_OPCODE_CLAMP:
+	case C_OPCODE_FLR:
+	case C_OPCODE_ROUND:
+	case C_OPCODE_EX2:
+	case C_OPCODE_LG2:
+	case C_OPCODE_POW:
+	case C_OPCODE_XPD:
+	case C_OPCODE_ABS:
+	case C_OPCODE_RCC:
+	case C_OPCODE_DPH:
+	case C_OPCODE_COS:
+	case C_OPCODE_DDX:
+	case C_OPCODE_DDY:
+	case C_OPCODE_PK2H:
+	case C_OPCODE_PK2US:
+	case C_OPCODE_PK4B:
+	case C_OPCODE_PK4UB:
+	case C_OPCODE_RFL:
+	case C_OPCODE_SEQ:
+	case C_OPCODE_SFL:
+	case C_OPCODE_SGT:
+	case C_OPCODE_SIN:
+	case C_OPCODE_SLE:
+	case C_OPCODE_SNE:
+	case C_OPCODE_STR:
+	case C_OPCODE_UP2H:
+	case C_OPCODE_UP2US:
+	case C_OPCODE_UP4B:
+	case C_OPCODE_UP4UB:
+	case C_OPCODE_X2D:
+	case C_OPCODE_ARA:
+	case C_OPCODE_ARR:
+	case C_OPCODE_BRA:
+	case C_OPCODE_SSG:
+	case C_OPCODE_CMP:
+	case C_OPCODE_SCS:
+	case C_OPCODE_NRM:
+	case C_OPCODE_DIV:
+	case C_OPCODE_DP2:
+	case C_OPCODE_CEIL:
+	case C_OPCODE_I2F:
+	case C_OPCODE_NOT:
+	case C_OPCODE_TRUNC:
+	case C_OPCODE_SHL:
+	case C_OPCODE_AND:
+	case C_OPCODE_OR:
+	case C_OPCODE_MOD:
+	case C_OPCODE_XOR:
+	case C_OPCODE_SAD:
+	case C_OPCODE_NRM4:
+	case C_OPCODE_F2I:
+	case C_OPCODE_IDIV:
+	case C_OPCODE_IMAX:
+	case C_OPCODE_IMIN:
+	case C_OPCODE_INEG:
+	case C_OPCODE_ISGE:
+	case C_OPCODE_ISHR:
+	case C_OPCODE_ISLT:
+	case C_OPCODE_F2U:
+	case C_OPCODE_U2F:
+	case C_OPCODE_UADD:
+	case C_OPCODE_UDIV:
+	case C_OPCODE_UMAD:
+	case C_OPCODE_UMAX:
+	case C_OPCODE_UMIN:
+	case C_OPCODE_UMOD:
+	case C_OPCODE_UMUL:
+	case C_OPCODE_USEQ:
+	case C_OPCODE_USGE:
+	case C_OPCODE_USHR:
+	case C_OPCODE_USLT:
+	case C_OPCODE_USNE:
+		return 1;
+	case C_OPCODE_END:
+	case C_OPCODE_VFETCH:
+	case C_OPCODE_KILP:
+	case C_OPCODE_CAL:
+	case C_OPCODE_RET:
+	case C_OPCODE_TXB:
+	case C_OPCODE_TXL:
+	case C_OPCODE_BRK:
+	case C_OPCODE_IF:
+	case C_OPCODE_BGNFOR:
+	case C_OPCODE_REP:
+	case C_OPCODE_ELSE:
+	case C_OPCODE_ENDIF:
+	case C_OPCODE_ENDFOR:
+	case C_OPCODE_ENDREP:
+	case C_OPCODE_PUSHA:
+	case C_OPCODE_POPA:
+	case C_OPCODE_TXF:
+	case C_OPCODE_TXQ:
+	case C_OPCODE_CONT:
+	case C_OPCODE_EMIT:
+	case C_OPCODE_ENDPRIM:
+	case C_OPCODE_BGNLOOP:
+	case C_OPCODE_BGNSUB:
+	case C_OPCODE_ENDLOOP:
+	case C_OPCODE_ENDSUB:
+	case C_OPCODE_NOP:
+	case C_OPCODE_CALLNZ:
+	case C_OPCODE_IFC:
+	case C_OPCODE_BREAKC:
+	case C_OPCODE_KIL:
+	case C_OPCODE_TEX:
+	case C_OPCODE_TXD:
+	case C_OPCODE_TXP:
+	case C_OPCODE_SWITCH:
+	case C_OPCODE_CASE:
+	case C_OPCODE_DEFAULT:
+	case C_OPCODE_ENDSWITCH:
+	default:
+		return 0;
+	}
+}
+
+
+/* NEW */
+void c_node_init(struct c_node *node)
+{
+	memset(node, 0, sizeof(struct c_node));
+	c_list_init(&node->predecessors);
+	c_list_init(&node->successors);
+	c_list_init(&node->childs);
+	c_list_init(&node->insts);
+	node->parent = NULL;
+}
+
+static struct c_node_link *c_node_link_new(struct c_node *node)
+{
+	struct c_node_link *link;
+
+	link = calloc(1, sizeof(struct c_node_link));
+	if (link == NULL)
+		return NULL;
+	c_list_init(link);
+	link->node = node;
+	return link;
+}
+
+int c_node_cfg_link(struct c_node *predecessor, struct c_node *successor)
+{
+	struct c_node_link *pedge, *sedge;
+
+	pedge = c_node_link_new(successor);
+	sedge = c_node_link_new(predecessor);
+	if (sedge == NULL || pedge == NULL) {
+		free(sedge);
+		free(pedge);
+		return -ENOMEM;
+	}
+	c_list_add_tail(pedge, &predecessor->successors);
+	c_list_add_tail(sedge, &successor->predecessors);
+	return 0;
+}
+
+int c_node_add_new_instruction_head(struct c_node *node, struct c_instruction *instruction)
+{
+	struct c_instruction *inst = calloc(1, sizeof(struct c_instruction));
+
+	if (inst == NULL)
+		return -ENOMEM;
+	memcpy(inst, instruction, sizeof(struct c_instruction));
+	c_list_add(inst, &node->insts);
+	return 0;
+}
+
+int c_node_add_new_instruction(struct c_node *node, struct c_instruction *instruction)
+{
+	struct c_instruction *inst = calloc(1, sizeof(struct c_instruction));
+
+	if (inst == NULL)
+		return -ENOMEM;
+	memcpy(inst, instruction, sizeof(struct c_instruction));
+	c_list_add_tail(inst, &node->insts);
+	return 0;
+}
+
+struct c_node *c_shader_cfg_new_node_after(struct c_shader *shader, struct c_node *predecessor)
+{
+	struct c_node *node = calloc(1, sizeof(struct c_node));
+
+	if (node == NULL)
+		return NULL;
+	c_node_init(node);
+	if (c_node_cfg_link(predecessor, node)) {
+		free(node);
+		return NULL;
+	}
+	c_list_add_tail(node, &shader->nodes);
+	return node;
+}
+
+int c_shader_init(struct c_shader *shader, unsigned type)
+{
+	unsigned i;
+	int r;
+
+	shader->type = type;
+	for (i = 0; i < C_FILE_COUNT; i++) {
+		shader->files[i].nvectors = 0;
+		c_list_init(&shader->files[i].vectors);
+	}
+	c_list_init(&shader->nodes);
+	c_node_init(&shader->entry);
+	c_node_init(&shader->end);
+	shader->entry.opcode = C_OPCODE_ENTRY;
+	shader->end.opcode = C_OPCODE_END;
+	r = c_node_cfg_link(&shader->entry, &shader->end);
+	if (r)
+		return r;
+	return 0;
+}
+
+struct c_vector *c_shader_vector_new(struct c_shader *shader, unsigned file, unsigned name, int sid)
+{
+	struct c_vector *v = calloc(1, sizeof(struct c_vector));
+	int i;
+
+	if (v == NULL) {
+		return NULL;
+	}
+	for (i = 0; i < 4; i++) {
+		v->channel[i] = calloc(1, sizeof(struct c_channel));
+		if (v->channel[i] == NULL)
+			goto out_err;
+		v->channel[i]->vindex = i;
+		v->channel[i]->vector = v;
+	}
+	v->file = file;
+	v->name = name;
+	v->sid = sid;
+	shader->files[v->file].nvectors++;
+	v->id = shader->nvectors++;
+	c_list_add_tail(v, &shader->files[v->file].vectors);
+	return v;
+out_err:
+	for (i = 0; i < 4; i++) {
+		free(v->channel[i]);
+	}
+	free(v);
+	return NULL;
+}
+
+static void c_node_remove_link(struct c_node_link *head, struct c_node *node)
+{
+	struct c_node_link *link, *tmp;
+
+	c_list_for_each_safe(link, tmp, head) {
+		if (link->node == node) {
+			c_list_del(link);
+			free(link);
+		}
+	}
+}
+
+static void c_node_destroy(struct c_node *node)
+{
+	struct c_instruction *i, *ni;
+	struct c_node_link *link, *tmp;
+
+	c_list_for_each_safe(i, ni, &node->insts) {
+		c_list_del(i);
+		free(i);
+	}
+	if (node->parent)
+		c_node_remove_link(&node->parent->childs, node);
+	node->parent = NULL;
+	c_list_for_each_safe(link, tmp, &node->predecessors) {
+		c_node_remove_link(&link->node->successors, node);
+		c_list_del(link);
+		free(link);
+	}
+	c_list_for_each_safe(link, tmp, &node->successors) {
+		c_node_remove_link(&link->node->predecessors, node);
+		c_list_del(link);
+		free(link);
+	}
+	c_list_for_each_safe(link, tmp, &node->childs) {
+		link->node->parent = NULL;
+		c_list_del(link);
+		free(link);
+	}
+}
+
+void c_shader_destroy(struct c_shader *shader)
+{
+	struct c_node *n, *nn;
+	struct c_vector *v, *nv;
+	unsigned i;
+
+	for (i = 0; i < C_FILE_COUNT; i++) {
+		shader->files[i].nvectors = 0;
+		c_list_for_each_safe(v, nv, &shader->files[i].vectors) {
+			c_list_del(v);
+			free(v->channel[0]);
+			free(v->channel[1]);
+			free(v->channel[2]);
+			free(v->channel[3]);
+			free(v);
+		}
+	}
+	c_list_for_each_safe(n, nn, &shader->nodes) {
+		c_list_del(n);
+		c_node_destroy(n);
+	}
+	memset(shader, 0, sizeof(struct c_shader));
+}
+
+static void c_shader_dfs_without_rec(struct c_node *entry, struct c_node *node)
+{
+	struct c_node_link *link;
+
+	if (entry == node || entry->visited)
+		return;
+	entry->visited = 1;
+	c_list_for_each(link, &entry->successors) {
+		c_shader_dfs_without_rec(link->node, node);
+	}
+}
+
+static void c_shader_dfs_without(struct c_shader *shader, struct c_node *node)
+{
+	struct c_node *n;
+
+	shader->entry.visited = 0;
+	shader->end.visited = 0;
+	c_list_for_each(n, &shader->nodes) {
+		n->visited = 0;
+	}
+	c_shader_dfs_without_rec(&shader->entry, node);
+}
+
+static int c_shader_build_dominator_tree_rec(struct c_shader *shader, struct c_node *node)
+{
+	struct c_node_link *link, *nlink;
+	unsigned found = 0;
+	int r;
+
+	if (node->done)
+		return 0;
+	node->done = 1;
+	c_list_for_each(link, &node->predecessors) {
+		/* if we remove this predecessor can we reach the current node ? */
+		c_shader_dfs_without(shader, link->node);
+		if (node->visited == 0) {
+			/* we were unable to visit current node thus current
+			 * predecessor  is the immediate dominator of node, as
+			 * their can be only one immediate dominator we break
+			 */
+			node->parent = link->node;
+			nlink = c_node_link_new(node);
+			if (nlink == NULL)
+				return -ENOMEM;
+			c_list_add_tail(nlink, &link->node->childs);
+			found = 1;
+			break;
+		}
+	}
+	/* this shouldn't happen there should at least be 1 denominator for each node */
+	if (!found && node->opcode != C_OPCODE_ENTRY) {
+		fprintf(stderr, "invalid flow control graph node %p (%d) has no immediate dominator\n",
+			node, node->opcode);
+		return -EINVAL;
+	}
+	c_list_for_each(link, &node->predecessors) {
+		r = c_shader_build_dominator_tree_rec(shader, link->node);
+		if (r)
+			return r;
+	}
+	return 0;
+}
+
+int c_shader_build_dominator_tree(struct c_shader *shader)
+{
+	struct c_node *node;
+	c_list_for_each(node, &shader->nodes) {
+		node->done = 0;
+	}
+	return c_shader_build_dominator_tree_rec(shader, &shader->end);
+}