[Intel-gfx] [PATCH] drm/i915: Use hash tables for the command parser

Thu May 8 15:52:28 CEST 2014

On Thu, May 08, 2014 at 12:44:57PM +0100, Damien Lespiau wrote:
> I was hoping we could compute a (near) minimal perfect hash function
> though. Let me try to dig a bit.

So, I went a bit further here and we can actually generate a minimal
perfect hash function. I took the 44 HSW render opcodes and fed them
into:

  http://burtleburtle.net/bob/hash/perfect.html
  https://github.com/driedfruit/jenkins-minimal-perfect-hash

The resulting hash function is:

static uint8_t mph_tab[] = {
        0,0,10,0,51,0,34,0,12,22,0,0,28,0,9,0,
        9,0,19,0,0,0,11,0,10,61,20,50,49,60,45,55,
};

static uint32_t mph_hash(uint32_t val)
{
        uint32_t a, b, rsl;

        val += 0xa195a44b;
        val += (val << 8);
        val ^= (val >> 4);
        b = (val >> 18) & 0x1f;
        a = val >> 27;
        rsl = (a^mph_tab[b]);

        return rsl;
}

When used the 44 HSW opcodes (opcode & 0xffff0000) it produces distinct numbers
(perfect hash) from 0 to 43 (minimal) that could then be used to address an array.

You can play with the joined test:

$ ./minimal-hash-hsw-render  | sort -nk2

So now, how useful is that is an interesting question. We do have static tables
upstream (IIUC), but Tvrtko reminded me that it may not match other trees,
which is sad.

-- 
Damien
-------------- next part --------------
#include <stdint.h>
#include <stdio.h>

#define ARRAY_SIZE(x) (sizeof(x) / sizeof(*(x)))

#define MI_INSTR(opcode, flags) (((opcode) << 23) | (flags))

#define MI_NOOP			MI_INSTR(0, 0)
#define MI_USER_INTERRUPT	MI_INSTR(0x02, 0)
#define MI_WAIT_FOR_EVENT       MI_INSTR(0x03, 0)
#define MI_ARB_CHECK            MI_INSTR(0x05, 0)
#define MI_REPORT_HEAD		MI_INSTR(0x07, 0)
#define MI_ARB_ON_OFF		MI_INSTR(0x08, 0)
#define MI_BATCH_BUFFER_END	MI_INSTR(0x0a, 0)
#define MI_SUSPEND_FLUSH	MI_INSTR(0x0b, 0)
#define MI_OVERLAY_FLIP		MI_INSTR(0x11, 0)
#define MI_SET_PREDICATE        MI_INSTR(0x01, 0)
#define MI_ARB_CHECK            MI_INSTR(0x05, 0)
#define MI_RS_CONTROL           MI_INSTR(0x06, 0)
#define MI_URB_ATOMIC_ALLOC     MI_INSTR(0x09, 0)
#define MI_PREDICATE            MI_INSTR(0x0C, 0)
#define MI_RS_CONTEXT           MI_INSTR(0x0F, 0)
#define MI_TOPOLOGY_FILTER      MI_INSTR(0x0D, 0)
#define MI_LOAD_SCAN_LINES_EXCL MI_INSTR(0x13, 0)
#define MI_URB_CLEAR            MI_INSTR(0x19, 0)
#define MI_UPDATE_GTT           MI_INSTR(0x23, 0)
#define MI_CLFLUSH              MI_INSTR(0x27, 0)
#define MI_REPORT_PERF_COUNT    MI_INSTR(0x28, 0)
#define MI_LOAD_REGISTER_MEM    MI_INSTR(0x29, 0)
#define MI_LOAD_REGISTER_REG    MI_INSTR(0x2A, 0)
#define MI_RS_STORE_DATA_IMM    MI_INSTR(0x2B, 0)
#define MI_LOAD_URB_MEM         MI_INSTR(0x2C, 0)
#define MI_STORE_URB_MEM        MI_INSTR(0x2D, 0)
#define MI_CONDITIONAL_BATCH_BUFFER_END MI_INSTR(0x36, 0)
#define MI_SEMAPHORE_MBOX	MI_INSTR(0x16, 1) /* gen6+ */
#define MI_STORE_DWORD_IMM	MI_INSTR(0x20, 1)
#define MI_STORE_DWORD_INDEX	MI_INSTR(0x21, 1)
#define MI_SET_CONTEXT		MI_INSTR(0x18, 0)
#define MI_LOAD_REGISTER_IMM(x)	MI_INSTR(0x22, 2*(x)-1)
#define MI_STORE_REGISTER_MEM(x) MI_INSTR(0x24, 2*(x)-1)
#define MI_BATCH_BUFFER_START	MI_INSTR(0x31, 0)
#define MI_FLUSH		MI_INSTR(0x04, 0)
#define MI_DISPLAY_FLIP		MI_INSTR(0x14, 2)
#define MI_LOAD_SCAN_LINES_INCL MI_INSTR(0x12, 0)

#define GFX_OP_PIPE_CONTROL(len)	((0x3<<29)|(0x3<<27)|(0x2<<24)|(len-2))
#define PIPELINE_SELECT                ((0x3<<29)|(0x1<<27)|(0x1<<24)|(0x4<<16))
#define GFX_OP_3DSTATE_VF_STATISTICS   ((0x3<<29)|(0x1<<27)|(0x0<<24)|(0xB<<16))
#define MEDIA_VFE_STATE                ((0x3<<29)|(0x2<<27)|(0x0<<24)|(0x0<<16))
#define  MEDIA_VFE_STATE_MMIO_ACCESS_MASK (0x18)
#define GPGPU_OBJECT                   ((0x3<<29)|(0x2<<27)|(0x1<<24)|(0x4<<16))
#define GPGPU_WALKER                   ((0x3<<29)|(0x2<<27)|(0x1<<24)|(0x5<<16))
#define GFX_OP_3DSTATE_DX9_CONSTANTF_VS \
	((0x3<<29)|(0x3<<27)|(0x0<<24)|(0x39<<16))
#define GFX_OP_3DSTATE_DX9_CONSTANTF_PS \
	((0x3<<29)|(0x3<<27)|(0x0<<24)|(0x3A<<16))
#define GFX_OP_3DSTATE_SO_DECL_LIST \
	((0x3<<29)|(0x3<<27)|(0x1<<24)|(0x17<<16))

#define GFX_OP_3DSTATE_BINDING_TABLE_EDIT_VS \
	((0x3<<29)|(0x3<<27)|(0x0<<24)|(0x43<<16))
#define GFX_OP_3DSTATE_BINDING_TABLE_EDIT_GS \
	((0x3<<29)|(0x3<<27)|(0x0<<24)|(0x44<<16))
#define GFX_OP_3DSTATE_BINDING_TABLE_EDIT_HS \
	((0x3<<29)|(0x3<<27)|(0x0<<24)|(0x45<<16))
#define GFX_OP_3DSTATE_BINDING_TABLE_EDIT_DS \
	((0x3<<29)|(0x3<<27)|(0x0<<24)|(0x46<<16))
#define GFX_OP_3DSTATE_BINDING_TABLE_EDIT_PS \
	((0x3<<29)|(0x3<<27)|(0x0<<24)|(0x47<<16))

#define MFX_WAIT  ((0x3<<29)|(0x1<<27)|(0x0<<16))

#define COLOR_BLT     ((0x2<<29)|(0x40<<22))
#define SRC_COPY_BLT  ((0x2<<29)|(0x43<<22))

uint32_t opcodes[] = {
	MI_NOOP,
	MI_USER_INTERRUPT,
	MI_WAIT_FOR_EVENT,
	MI_ARB_CHECK,
	MI_REPORT_HEAD,
	MI_SUSPEND_FLUSH,
	MI_SEMAPHORE_MBOX,
	MI_STORE_DWORD_INDEX,
	MI_LOAD_REGISTER_IMM(1),
	MI_STORE_REGISTER_MEM(1),
	MI_LOAD_REGISTER_MEM,
	MI_BATCH_BUFFER_START,
	MI_FLUSH,
	MI_ARB_ON_OFF,
	MI_PREDICATE,
	MI_TOPOLOGY_FILTER,
	MI_DISPLAY_FLIP,
	MI_SET_CONTEXT,
	MI_URB_CLEAR,
	MI_STORE_DWORD_IMM,
	MI_UPDATE_GTT,
	MI_CLFLUSH,
	MI_REPORT_PERF_COUNT,
	MI_CONDITIONAL_BATCH_BUFFER_END,
	GFX_OP_3DSTATE_VF_STATISTICS,
	PIPELINE_SELECT,
	MEDIA_VFE_STATE,
	GPGPU_OBJECT,
	GPGPU_WALKER,
	GFX_OP_3DSTATE_SO_DECL_LIST,
	GFX_OP_PIPE_CONTROL(5),
	MI_LOAD_SCAN_LINES_INCL,
	MI_LOAD_SCAN_LINES_EXCL,
	MI_LOAD_REGISTER_REG,
	MI_RS_STORE_DATA_IMM,
	MI_LOAD_URB_MEM,
	MI_STORE_URB_MEM,
	GFX_OP_3DSTATE_DX9_CONSTANTF_VS,
	GFX_OP_3DSTATE_DX9_CONSTANTF_PS,
	GFX_OP_3DSTATE_BINDING_TABLE_EDIT_VS,
	GFX_OP_3DSTATE_BINDING_TABLE_EDIT_GS,
	GFX_OP_3DSTATE_BINDING_TABLE_EDIT_HS,
	GFX_OP_3DSTATE_BINDING_TABLE_EDIT_DS,
	GFX_OP_3DSTATE_BINDING_TABLE_EDIT_PS,
};

#define STD_MI_OPCODE_MASK  0xFF800000
#define STD_3D_OPCODE_MASK  0xFFFF0000
#define STD_2D_OPCODE_MASK  0xFFC00000
#define STD_MFX_OPCODE_MASK 0xFFFF0000
#define CMD_HASH_MASK STD_MI_OPCODE_MASK

/* small adjustments to _a_ to make values distinct */
static uint8_t mph_tab[] = {
	0,0,10,0,51,0,34,0,12,22,0,0,28,0,9,0,
	9,0,19,0,0,0,11,0,10,61,20,50,49,60,45,55,
};

/* The hash function */
static uint32_t mph_hash(uint32_t val)
{
	uint32_t a, b, rsl;
	val += 0xa195a44b;

	val += (val << 8);
	val ^= (val >> 4);
	b = (val >> 18) & 0x1f;
	a = val >> 27;
	rsl = (a^mph_tab[b]);

	return rsl;
}

int main(void)
{
	int i;

	for (i = 0; i < ARRAY_SIZE(opcodes); i++)
		printf("%08x %d\n", opcodes[i] & 0xffff0000,
			mph_hash(opcodes[i] & 0xffff0000));

	return 0;
}