static LLVMTypeRef llvmTypeForSignature(oThreadContextRef ctx, oSignatureRef sig) {
	uword i;
	LLVMTypeRef fnType, retType;
	oParameterRef* params = (oParameterRef*)oArrayDataPointer(sig->parameters);
	LLVMTypeRef* paramTypes = (LLVMTypeRef*)oMalloc(sizeof(LLVMTypeRef) * sig->parameters->num_elements);

	if(sig->retType->kind == o_T_OBJECT) {
		retType = LLVMPointerType(sig->retType->llvmType, 0);
	} else {
		retType = sig->retType->llvmType;
	}
	for(i = 0; i < sig->parameters->num_elements; ++i) {
		if(params[i]->type->kind == o_T_OBJECT) {
			paramTypes[i] = LLVMPointerType(params[i]->type->llvmType, 0);
		} else {
			paramTypes[i] = params[i]->type->llvmType;
		}
	}
	fnType = LLVMFunctionType(retType, paramTypes, sig->parameters->num_elements, o_false);
	oFree(paramTypes);
	return fnType;
}

void gendesc_basetype(compile_t* c, LLVMTypeRef desc_type)
{
  LLVMTypeRef params[DESC_LENGTH];

  params[DESC_ID] = c->i32;
  params[DESC_SIZE] = c->i32;
  params[DESC_TRAIT_COUNT] = c->i32;
  params[DESC_FIELD_COUNT] = c->i32;
  params[DESC_FIELD_OFFSET] = c->i32;
  params[DESC_TRACE] = c->trace_fn;
  params[DESC_SERIALISE] = c->trace_fn;
  params[DESC_DESERIALISE] = c->trace_fn;
  params[DESC_DISPATCH] = c->dispatch_fn;
  params[DESC_FINALISE] = c->final_fn;
  params[DESC_EVENT_NOTIFY] = c->i32;
  params[DESC_TRAITS] = LLVMPointerType(LLVMArrayType(c->i32, 0), 0);
  params[DESC_FIELDS] = LLVMPointerType(
    LLVMArrayType(c->field_descriptor, 0), 0);
  params[DESC_VTABLE] = LLVMArrayType(c->void_ptr, 0);

  LLVMStructSetBody(desc_type, params, DESC_LENGTH, false);
}

static LLVMValueRef make_field_list(compile_t* c, reach_type_t* t)
{
  // The list is an array of field descriptors.
  uint32_t count;

  if(t->underlying == TK_TUPLETYPE)
    count = t->field_count;
  else
    count = 0;

  LLVMTypeRef field_type = LLVMArrayType(c->field_descriptor, count);

  // If we aren't a tuple, return a null pointer to a list.
  if(count == 0)
    return LLVMConstNull(LLVMPointerType(field_type, 0));

  // Create a constant array of field descriptors.
  size_t buf_size = count * sizeof(LLVMValueRef);
  LLVMValueRef* list = (LLVMValueRef*)ponyint_pool_alloc_size(buf_size);

  for(uint32_t i = 0; i < count; i++)
  {
    LLVMValueRef fdesc[2];
    fdesc[0] = LLVMConstInt(c->i32,
      LLVMOffsetOfElement(c->target_data, t->primitive, i), false);

    if(t->fields[i].type->desc != NULL)
    {
      // We are a concrete type.
      fdesc[1] = LLVMConstBitCast(t->fields[i].type->desc,
        c->descriptor_ptr);
    } else {
      // We aren't a concrete type.
      fdesc[1] = LLVMConstNull(c->descriptor_ptr);
    }

    list[i] = LLVMConstStructInContext(c->context, fdesc, 2, false);
  }

  LLVMValueRef field_array = LLVMConstArray(c->field_descriptor, list, count);

  // Create a global to hold the array.
  const char* name = genname_fieldlist(t->name);
  LLVMValueRef global = LLVMAddGlobal(c->module, field_type, name);
  LLVMSetGlobalConstant(global, true);
  LLVMSetLinkage(global, LLVMPrivateLinkage);
  LLVMSetInitializer(global, field_array);

  ponyint_pool_free_size(buf_size, list);
  return global;
}

static bool dynamic_tuple_element(compile_t* c, LLVMValueRef ptr,
  LLVMValueRef desc, ast_t* pattern, LLVMBasicBlockRef next_block, int elem)
{
  // If we have a capture, generate the alloca now.
  switch(ast_id(pattern))
  {
    case TK_MATCH_CAPTURE:
      if(gen_localdecl(c, pattern) == NULL)
        return false;
      break;

    default: {}
  }

  // Get the field offset and field descriptor from the tuple descriptor.
  LLVMValueRef field_info = gendesc_fieldinfo(c, desc, elem);
  LLVMValueRef field_ptr = gendesc_fieldptr(c, ptr, field_info);
  LLVMValueRef field_desc = gendesc_fielddesc(c, field_info);

  // If we have a null descriptor, load the object.
  LLVMBasicBlockRef null_block = codegen_block(c, "null_desc");
  LLVMBasicBlockRef nonnull_block = codegen_block(c, "nonnull_desc");
  LLVMBasicBlockRef continue_block = codegen_block(c, "merge_desc");
  LLVMValueRef test = LLVMBuildIsNull(c->builder, field_desc, "");
  LLVMBuildCondBr(c->builder, test, null_block, nonnull_block);

  // Load the object, load its descriptor, and continue from there.
  LLVMPositionBuilderAtEnd(c->builder, null_block);
  LLVMTypeRef ptr_type = LLVMPointerType(c->object_ptr, 0);
  LLVMValueRef object_ptr = LLVMBuildIntToPtr(c->builder, field_ptr, ptr_type,
    "");
  LLVMValueRef object = LLVMBuildLoad(c->builder, object_ptr, "");
  LLVMValueRef object_desc = gendesc_fetch(c, object);

  if(!dynamic_match_object(c, object, object_desc, pattern, next_block))
    return false;

  LLVMBuildBr(c->builder, continue_block);

  // Continue with the pointer and descriptor.
  LLVMPositionBuilderAtEnd(c->builder, nonnull_block);

  if(!dynamic_match_ptr(c, field_ptr, field_desc, pattern, next_block))
    return false;

  LLVMBuildBr(c->builder, continue_block);

  // Merge the two branches.
  LLVMPositionBuilderAtEnd(c->builder, continue_block);
  return true;
}

/*
 * Build LLVM function that exercises the unary operator builder.
 */
static LLVMValueRef
build_unary_test_func(struct gallivm_state *gallivm,
                      const struct unary_test_t *test)
{
   struct lp_type type = lp_type_float_vec(32, lp_native_vector_width);
   LLVMContextRef context = gallivm->context;
   LLVMModuleRef module = gallivm->module;
   LLVMTypeRef vf32t = lp_build_vec_type(gallivm, type);
   LLVMTypeRef args[2] = { LLVMPointerType(vf32t, 0), LLVMPointerType(vf32t, 0) };
   LLVMValueRef func = LLVMAddFunction(module, test->name,
                                       LLVMFunctionType(LLVMVoidTypeInContext(context),
                                                        args, Elements(args), 0));
   LLVMValueRef arg0 = LLVMGetParam(func, 0);
   LLVMValueRef arg1 = LLVMGetParam(func, 1);
   LLVMBuilderRef builder = gallivm->builder;
   LLVMBasicBlockRef block = LLVMAppendBasicBlockInContext(context, func, "entry");
   LLVMValueRef ret;

   struct lp_build_context bld;

   lp_build_context_init(&bld, gallivm, type);

   LLVMSetFunctionCallConv(func, LLVMCCallConv);

   LLVMPositionBuilderAtEnd(builder, block);
   
   arg1 = LLVMBuildLoad(builder, arg1, "");

   ret = test->builder(&bld, arg1);
   
   LLVMBuildStore(builder, ret, arg0);

   LLVMBuildRetVoid(builder);

   gallivm_verify_function(gallivm, func);

   return func;
}

static void make_box_type(compile_t* c, gentype_t* g)
{
  if(g->primitive == NULL)
    return;

  if(g->structure == NULL)
  {
    const char* box_name = genname_box(g->type_name);
    g->structure = LLVMGetTypeByName(c->module, box_name);

    if(g->structure == NULL)
      g->structure = LLVMStructCreateNamed(c->context, box_name);
  }

  if(LLVMIsOpaqueStruct(g->structure))
  {
    LLVMTypeRef elements[2];
    elements[0] = LLVMPointerType(g->desc_type, 0);
    elements[1] = g->primitive;
    LLVMStructSetBody(g->structure, elements, 2, false);
  }

  g->structure_ptr = LLVMPointerType(g->structure, 0);
}

static LLVMValueRef make_trait_list(compile_t* c, gentype_t* g)
{
  // The list is an array of integers.
  uint32_t count = trait_count(c, g);

  // If we have no traits, return a null pointer to a list.
  if(count == 0)
    return LLVMConstNull(LLVMPointerType(LLVMArrayType(c->i32, 0), 0));

  // Sort the trait identifiers.
  size_t tid_size = count * sizeof(uint32_t);
  uint32_t* tid = (uint32_t*)pool_alloc_size(tid_size);

  reachable_type_t* t = reach_type(c->reachable, g->type_name);
  assert(t != NULL);

  size_t i = HASHMAP_BEGIN;
  size_t index = 0;
  reachable_type_t* provide;

  while((provide = reachable_type_cache_next(&t->subtypes, &i)) != NULL)
    tid[index++] = provide->type_id;

  qsort(tid, index, sizeof(uint32_t), cmp_uint32);
  index = unique_uint32(tid, index);

  // Create a constant array of trait identifiers.
  size_t list_size = index * sizeof(LLVMValueRef);
  LLVMValueRef* list = (LLVMValueRef*)pool_alloc_size(list_size);

  for(i = 0; i < index; i++)
    list[i] = LLVMConstInt(c->i32, tid[i], false);

  count = (uint32_t)index;
  LLVMValueRef trait_array = LLVMConstArray(c->i32, list, count);

  // Create a global to hold the array.
  const char* name = genname_traitlist(g->type_name);
  LLVMTypeRef type = LLVMArrayType(c->i32, count);
  LLVMValueRef global = LLVMAddGlobal(c->module, type, name);
  LLVMSetGlobalConstant(global, true);
  LLVMSetLinkage(global, LLVMInternalLinkage);
  LLVMSetInitializer(global, trait_array);

  pool_free_size(tid_size, tid);
  pool_free_size(list_size, list);
  return global;
}

static void trace_array_elements(compile_t* c, reach_type_t* t,
  LLVMValueRef ctx, LLVMValueRef object, LLVMValueRef pointer)
{
  // Get the type argument for the array. This will be used to generate the
  // per-element trace call.
  ast_t* typeargs = ast_childidx(t->ast, 2);
  ast_t* typearg = ast_child(typeargs);

  if(!gentrace_needed(typearg))
    return;

  reach_type_t* t_elem = reach_type(c->reach, typearg);
  pointer = LLVMBuildBitCast(c->builder, pointer,
    LLVMPointerType(t_elem->use_type, 0), "");

  LLVMBasicBlockRef entry_block = LLVMGetInsertBlock(c->builder);
  LLVMBasicBlockRef cond_block = codegen_block(c, "cond");
  LLVMBasicBlockRef body_block = codegen_block(c, "body");
  LLVMBasicBlockRef post_block = codegen_block(c, "post");

  // Read the size.
  LLVMValueRef size = field_value(c, object, 1);
  LLVMBuildBr(c->builder, cond_block);

  // While the index is less than the size, trace an element. The initial
  // index when coming from the entry block is zero.
  LLVMPositionBuilderAtEnd(c->builder, cond_block);
  LLVMValueRef phi = LLVMBuildPhi(c->builder, c->intptr, "");
  LLVMValueRef zero = LLVMConstInt(c->intptr, 0, false);
  LLVMAddIncoming(phi, &zero, &entry_block, 1);
  LLVMValueRef test = LLVMBuildICmp(c->builder, LLVMIntULT, phi, size, "");
  LLVMBuildCondBr(c->builder, test, body_block, post_block);

  // The phi node is the index. Get the element and trace it.
  LLVMPositionBuilderAtEnd(c->builder, body_block);
  LLVMValueRef elem_ptr = LLVMBuildGEP(c->builder, pointer, &phi, 1, "elem");
  LLVMValueRef elem = LLVMBuildLoad(c->builder, elem_ptr, "");
  gentrace(c, ctx, elem, typearg);

  // Add one to the phi node and branch back to the cond block.
  LLVMValueRef one = LLVMConstInt(c->intptr, 1, false);
  LLVMValueRef inc = LLVMBuildAdd(c->builder, phi, one, "");
  body_block = LLVMGetInsertBlock(c->builder);
  LLVMAddIncoming(phi, &inc, &body_block, 1);
  LLVMBuildBr(c->builder, cond_block);

  LLVMPositionBuilderAtEnd(c->builder, post_block);
}

static LLVMValueRef llvm_load_const_buffer(
	struct lp_build_tgsi_context * bld_base,
	LLVMValueRef OffsetValue,
	unsigned ConstantAddressSpace)
{
	LLVMValueRef offset[2] = {
		LLVMConstInt(LLVMInt64TypeInContext(bld_base->base.gallivm->context), 0, false),
		OffsetValue
	};

	LLVMTypeRef const_ptr_type = LLVMPointerType(LLVMArrayType(LLVMVectorType(bld_base->base.elem_type, 4), 1024),
							ConstantAddressSpace);
	LLVMValueRef const_ptr = LLVMBuildIntToPtr(bld_base->base.gallivm->builder, lp_build_const_int32(bld_base->base.gallivm, 0), const_ptr_type, "");
	LLVMValueRef ptr = LLVMBuildGEP(bld_base->base.gallivm->builder, const_ptr, offset, 2, "");
	return LLVMBuildLoad(bld_base->base.gallivm->builder, ptr, "");
}

static void pointer_delete(compile_t* c, reach_type_t* t, reach_type_t* t_elem)
{
  FIND_METHOD("_delete");

  LLVMTypeRef params[3];
  params[0] = t->use_type;
  params[1] = c->intptr;
  params[2] = c->intptr;
  start_function(c, m, t_elem->use_type, params, 3);

  // Set up a constant integer for the allocation size.
  size_t size = (size_t)LLVMABISizeOfType(c->target_data, t_elem->use_type);
  LLVMValueRef l_size = LLVMConstInt(c->intptr, size, false);

  LLVMValueRef ptr = LLVMGetParam(m->func, 0);
  LLVMValueRef n = LLVMGetParam(m->func, 1);
  LLVMValueRef len = LLVMGetParam(m->func, 2);

  LLVMValueRef elem_ptr = LLVMBuildBitCast(c->builder, ptr,
    LLVMPointerType(t_elem->use_type, 0), "");
  LLVMValueRef result = LLVMBuildLoad(c->builder, elem_ptr, "");

  LLVMValueRef dst = LLVMBuildPtrToInt(c->builder, elem_ptr, c->intptr, "");
  LLVMValueRef offset = LLVMBuildMul(c->builder, n, l_size, "");
  LLVMValueRef src = LLVMBuildAdd(c->builder, dst, offset, "");
  LLVMValueRef elen = LLVMBuildMul(c->builder, len, l_size, "");

  LLVMValueRef args[5];
  args[0] = LLVMBuildIntToPtr(c->builder, dst, c->void_ptr, "");
  args[1] = LLVMBuildIntToPtr(c->builder, src, c->void_ptr, "");
  args[2] = elen;
  args[3] = LLVMConstInt(c->i32, 1, false);
  args[4] = LLVMConstInt(c->i1, 0, false);

  // llvm.memmove.*(ptr, ptr + (n * sizeof(elem)), len * sizeof(elem))
  if(target_is_ilp32(c->opt->triple))
  {
    gencall_runtime(c, "llvm.memmove.p0i8.p0i8.i32", args, 5, "");
  } else {
    gencall_runtime(c, "llvm.memmove.p0i8.p0i8.i64", args, 5, "");
  }

  // Return ptr[0].
  LLVMBuildRet(c->builder, result);
  codegen_finishfun(c);
}

static LLVMValueRef 
translateIdLval(SymbolTable *TyTable, SymbolTable *ValTable, ASTNode *Node) {
  Type *IdType = (Type*) symTableFind(ValTable, Node->Value);
  LLVMValueRef IdValue;

  if (IdType->EscapedLevel > 0) {
    LLVMTypeRef LLVMType = getLLVMTypeFromType(TyTable, IdType);
    LLVMValueRef EVPtr   = getEscapedVar(ValTable, Node->Value, Node->EscapedLevel);
    LLVMValueRef EVLoad  = LLVMBuildLoad(Builder, EVPtr, "");

    IdValue = LLVMBuildBitCast(Builder, EVLoad, LLVMPointerType(LLVMType, 0), "");
  } else {
    IdValue = resolveAliasId(ValTable, Node->Value, &toValName, &symTableFindLocal);
  }

  return IdValue;
}

/**
 * lp_build_assert.
 *
 * Build an assertion in LLVM IR by building a function call to the
 * lp_assert() function above.
 *
 * \param condition should be an 'i1' or 'i32' value
 * \param msg  a string to print if the assertion fails.
 */
LLVMValueRef
lp_build_assert(LLVMBuilderRef builder, LLVMValueRef condition,
                const char *msg)
{
   LLVMModuleRef module;
   LLVMTypeRef arg_types[2];
   LLVMValueRef msg_string, assert_func, params[2], r;

   module = LLVMGetGlobalParent(LLVMGetBasicBlockParent(
                            LLVMGetInsertBlock(builder)));

   msg_string = lp_build_const_string_variable(module, msg, strlen(msg) + 1);

   arg_types[0] = LLVMInt32Type();
   arg_types[1] = LLVMPointerType(LLVMInt8Type(), 0);

   /* lookup the lp_assert function */
   assert_func = LLVMGetNamedFunction(module, "lp_assert");

   /* Create the assertion function if not found */
   if (!assert_func) {
      LLVMTypeRef func_type =
         LLVMFunctionType(LLVMVoidType(), arg_types, 2, 0);

      assert_func = LLVMAddFunction(module, "lp_assert", func_type);
      LLVMSetFunctionCallConv(assert_func, LLVMCCallConv);
      LLVMSetLinkage(assert_func, LLVMExternalLinkage);
      LLVMAddGlobalMapping(lp_build_engine, assert_func,
                           func_to_pointer((func_pointer)lp_assert));
   }
   assert(assert_func);

   /* build function call param list */
   params[0] = LLVMBuildZExt(builder, condition, arg_types[0], "");
   params[1] = LLVMBuildBitCast(builder, msg_string, arg_types[1], "");

   /* check arg types */
   assert(LLVMTypeOf(params[0]) == arg_types[0]);
   assert(LLVMTypeOf(params[1]) == arg_types[1]);

   r = LLVMBuildCall(builder, assert_func, params, 2, "");

   return r;
}

static void pointer_update(compile_t* c, reach_type_t* t, reach_type_t* t_elem)
{
  FIND_METHOD("_update");

  LLVMTypeRef params[3];
  params[0] = t->use_type;
  params[1] = c->intptr;
  params[2] = t_elem->use_type;
  start_function(c, m, t_elem->use_type, params, 3);

  LLVMValueRef ptr = LLVMGetParam(m->func, 0);
  LLVMValueRef index = LLVMGetParam(m->func, 1);

  LLVMValueRef elem_ptr = LLVMBuildBitCast(c->builder, ptr,
    LLVMPointerType(t_elem->use_type, 0), "");
  LLVMValueRef loc = LLVMBuildGEP(c->builder, elem_ptr, &index, 1, "");
  LLVMValueRef result = LLVMBuildLoad(c->builder, loc, "");
  LLVMBuildStore(c->builder, LLVMGetParam(m->func, 2), loc);

  LLVMBuildRet(c->builder, result);
  codegen_finishfun(c);
}

LLVMValueRef gen_call(struct node *ast)
{
	LLVMValueRef func, *arg_list = NULL;
	struct node *n;
	int arg_count, i;

	func = LLVMBuildBitCast(builder,
			rvalue_to_lvalue(codegen(ast->one)),
			LLVMPointerType(TYPE_FUNC, 0),
			"");

	arg_count = count_chain(ast->two);
	arg_list = calloc(sizeof(LLVMValueRef), arg_count);

	if (arg_count > 0 && arg_list == NULL)
		generror("out of memory");

	for (i = 0, n = ast->two; i < arg_count; i++, n = n->two)
		arg_list[arg_count - i - 1] = codegen(n->one);

	return LLVMBuildCall(builder, func, arg_list, arg_count, "");
}

static bool dynamic_value_ptr(compile_t* c, LLVMValueRef ptr,
  LLVMValueRef desc, ast_t* pattern, LLVMBasicBlockRef next_block)
{
  // Get the type of the right-hand side of the pattern's eq() function.
  ast_t* param_type = eq_param_type(c, pattern);

  // Check the runtime type. We pass a pointer to the fields because we may
  // still need to match a tuple type inside a type expression.
  if(!check_type(c, ptr, desc, param_type, next_block))
    return false;

  // We now know that ptr points to something of type pattern_type, and that
  // it isn't a boxed primitive, as that would go through the other path, ie
  // dynamic_match_object(). We also know it isn't an unboxed tuple. We can
  // load from ptr with a type based on the static type of the pattern.
  reach_type_t* t = reach_type(c->reach, param_type);
  LLVMTypeRef ptr_type = LLVMPointerType(t->use_type, 0);
  ptr = LLVMBuildIntToPtr(c->builder, ptr, ptr_type, "");
  LLVMValueRef value = LLVMBuildLoad(c->builder, ptr, "");

  return check_value(c, pattern, param_type, value, next_block);
}

/**
 * Gather elements from scatter positions in memory into a single vector.
 *
 * @param src_width src element width
 * @param dst_width result element width (source will be expanded to fit)
 * @param length length of the offsets,
 * @param base_ptr base pointer, should be a i8 pointer type.
 * @param offsets vector with offsets
 */
LLVMValueRef
lp_build_gather(LLVMBuilderRef builder,
                unsigned length,
                unsigned src_width,
                unsigned dst_width,
                LLVMValueRef base_ptr,
                LLVMValueRef offsets)
{
   LLVMTypeRef src_type = LLVMIntType(src_width);
   LLVMTypeRef src_ptr_type = LLVMPointerType(src_type, 0);
   LLVMTypeRef dst_elem_type = LLVMIntType(dst_width);
   LLVMTypeRef dst_vec_type = LLVMVectorType(dst_elem_type, length);
   LLVMValueRef res;
   unsigned i;

   res = LLVMGetUndef(dst_vec_type);
   for(i = 0; i < length; ++i) {
      LLVMValueRef index = LLVMConstInt(LLVMInt32Type(), i, 0);
      LLVMValueRef elem_offset;
      LLVMValueRef elem_ptr;
      LLVMValueRef elem;

      elem_offset = LLVMBuildExtractElement(builder, offsets, index, "");
      elem_ptr = LLVMBuildGEP(builder, base_ptr, &elem_offset, 1, "");
      elem_ptr = LLVMBuildBitCast(builder, elem_ptr, src_ptr_type, "");
      elem = LLVMBuildLoad(builder, elem_ptr, "");

      assert(src_width <= dst_width);
      if(src_width > dst_width)
         elem = LLVMBuildTrunc(builder, elem, dst_elem_type, "");
      if(src_width < dst_width)
         elem = LLVMBuildZExt(builder, elem, dst_elem_type, "");

      res = LLVMBuildInsertElement(builder, res, elem, index, "");
   }

   return res;
}

static LLVMValueRef dispatch_function(compile_t* c, ast_t* from, gentype_t* g,
  LLVMValueRef l_value, const char* method_name, ast_t* typeargs)
{
  LLVMValueRef func;

  if(g->use_type == c->object_ptr)
  {
    // Virtual, get the function by selector colour.
    uint32_t index = genfun_vtable_index(c, g, method_name, typeargs);
    assert(index != (uint32_t)-1);

    // Get the function from the vtable.
    func = gendesc_vtable(c, l_value, index);

    // Cast to the right function type.
    LLVMTypeRef f_type = genfun_sig(c, g, method_name, typeargs);

    if(f_type == NULL)
    {
      ast_error(from, "couldn't create a signature for '%s'", method_name);
      return NULL;
    }

    f_type = LLVMPointerType(f_type, 0);
    func = LLVMBuildBitCast(c->builder, func, f_type, "method");
  } else {
    // Static, get the actual function.
    func = genfun_proto(c, g, method_name, typeargs);

    if(func == NULL)
    {
      ast_error(from, "couldn't locate '%s'", method_name);
      return NULL;
    }
  }

  return func;
}

static bool dynamic_capture_ptr(compile_t* c, LLVMValueRef ptr,
  LLVMValueRef desc, ast_t* pattern, LLVMBasicBlockRef next_block)
{
  // Here, ptr is a pointer to a tuple field. It could be a primitive, an
  // object, or a nested tuple.
  ast_t* pattern_type = ast_type(pattern);

  // Check the runtime type. We pass a pointer to the fields because we may
  // still need to match a tuple type inside a type expression.
  if(!check_type(c, ptr, desc, pattern_type, next_block))
    return false;

  // We now know that ptr points to something of type pattern_type, and that
  // it isn't a boxed primitive or tuple, as that would go through the other
  // path, ie dynamic_match_object(). We also know it isn't an unboxed tuple.
  // We can load from ptr with a type based on the static type of the pattern.
  reach_type_t* t = reach_type(c->reach, pattern_type);
  LLVMTypeRef ptr_type = LLVMPointerType(t->use_type, 0);
  ptr = LLVMBuildIntToPtr(c->builder, ptr, ptr_type, "");
  LLVMValueRef value = LLVMBuildLoad(c->builder, ptr, "");

  return gen_assign_value(c, pattern, value, pattern_type) != NULL;
}

static LLVMValueRef make_trait_list(compile_t* c, gentype_t* g)
{
  // The list is an array of integers.
  uint32_t count = trait_count(c, g);
  LLVMTypeRef type = LLVMArrayType(c->i32, count);

  // If we have no traits, return a null pointer to a list.
  if(count == 0)
    return LLVMConstNull(LLVMPointerType(type, 0));

  // Create a constant array of trait identifiers.
  size_t buf_size = count *sizeof(LLVMValueRef);
  LLVMValueRef* list = (LLVMValueRef*)pool_alloc_size(buf_size);

  reachable_type_t* t = reach_type(c->reachable, g->type_name);
  assert(t != NULL);

  size_t i = HASHMAP_BEGIN;
  size_t index = 0;
  reachable_type_t* provide;

  while((provide = reachable_type_cache_next(&t->subtypes, &i)) != NULL)
    list[index++] = make_type_id(c, provide->name);

  LLVMValueRef trait_array = LLVMConstArray(c->i32, list, count);

  // Create a global to hold the array.
  const char* name = genname_traitlist(g->type_name);
  LLVMValueRef global = LLVMAddGlobal(c->module, type, name);
  LLVMSetGlobalConstant(global, true);
  LLVMSetLinkage(global, LLVMInternalLinkage);
  LLVMSetInitializer(global, trait_array);

  pool_free_size(buf_size, list);
  return global;
}

/**
 * Get the pointer to one element from scatter positions in memory.
 *
 * @sa lp_build_gather()
 */
LLVMValueRef
lp_build_gather_elem_ptr(struct gallivm_state *gallivm,
                         unsigned length,
                         LLVMValueRef base_ptr,
                         LLVMValueRef offsets,
                         unsigned i)
{
   LLVMValueRef offset;
   LLVMValueRef ptr;

   assert(LLVMTypeOf(base_ptr) == LLVMPointerType(LLVMInt8TypeInContext(gallivm->context), 0));

   if (length == 1) {
      assert(i == 0);
      offset = offsets;
   } else {
      LLVMValueRef index = lp_build_const_int32(gallivm, i);
      offset = LLVMBuildExtractElement(gallivm->builder, offsets, index, "");
   }

   ptr = LLVMBuildGEP(gallivm->builder, base_ptr, &offset, 1, "");

   return ptr;
}