*/
#include "util/u_debug.h"
+#include "util/u_memory.h"
#include "lp_bld_type.h"
#include "lp_bld_flow.h"
+#define LP_BUILD_FLOW_MAX_VARIABLES 32
+#define LP_BUILD_FLOW_MAX_DEPTH 32
+
+/**
+ * Enumeration of all possible flow constructs.
+ */
+enum lp_build_flow_construct_kind {
+ LP_BUILD_FLOW_SCOPE,
+ LP_BUILD_FLOW_SKIP,
+ LP_BUILD_FLOW_IF
+};
+
+
+/**
+ * Variable declaration scope.
+ */
+struct lp_build_flow_scope
+{
+ /** Number of variables declared in this scope */
+ unsigned num_variables;
+};
+
+
+/**
+ * Early exit. Useful to skip to the end of a function or block when
+ * the execution mask becomes zero or when there is an error condition.
+ */
+struct lp_build_flow_skip
+{
+ /** Block to skip to */
+ LLVMBasicBlockRef block;
+
+ /** Number of variables declared at the beginning */
+ unsigned num_variables;
+
+ LLVMValueRef *phi; /**< array [num_variables] */
+};
+
+
+/**
+ * if/else/endif.
+ */
+struct lp_build_flow_if
+{
+ unsigned num_variables;
+
+ LLVMValueRef *phi; /**< array [num_variables] */
+
+ LLVMValueRef condition;
+ LLVMBasicBlockRef entry_block, true_block, false_block, merge_block;
+};
+
+
+/**
+ * Union of all possible flow constructs' data
+ */
+union lp_build_flow_construct_data
+{
+ struct lp_build_flow_scope scope;
+ struct lp_build_flow_skip skip;
+ struct lp_build_flow_if ifthen;
+};
+
+
+/**
+ * Element of the flow construct stack.
+ */
+struct lp_build_flow_construct
+{
+ enum lp_build_flow_construct_kind kind;
+ union lp_build_flow_construct_data data;
+};
+
+
+/**
+ * All necessary data to generate LLVM control flow constructs.
+ *
+ * Besides keeping track of the control flow construct themselves we also
+ * need to keep track of variables in order to generate SSA Phi values.
+ */
+struct lp_build_flow_context
+{
+ LLVMBuilderRef builder;
+
+ /**
+ * Control flow stack.
+ */
+ struct lp_build_flow_construct constructs[LP_BUILD_FLOW_MAX_DEPTH];
+ unsigned num_constructs;
+
+ /**
+ * Variable stack
+ */
+ LLVMValueRef *variables[LP_BUILD_FLOW_MAX_VARIABLES];
+ unsigned num_variables;
+};
+
+
+struct lp_build_flow_context *
+lp_build_flow_create(LLVMBuilderRef builder)
+{
+ struct lp_build_flow_context *flow;
+
+ flow = CALLOC_STRUCT(lp_build_flow_context);
+ if(!flow)
+ return NULL;
+
+ flow->builder = builder;
+
+ return flow;
+}
+
+
void
-lp_build_mask_begin(struct lp_build_mask_context *mask,
- LLVMBuilderRef builder,
- union lp_type type,
- LLVMValueRef value)
+lp_build_flow_destroy(struct lp_build_flow_context *flow)
{
- memset(mask, 0, sizeof *mask);
+ assert(flow->num_constructs == 0);
+ assert(flow->num_variables == 0);
+ FREE(flow);
+}
- mask->builder = builder;
- mask->reg_type = LLVMIntType(type.width * type.length);
- mask->value = value;
+
+/**
+ * Begin/push a new flow control construct, such as a loop, skip block
+ * or variable scope.
+ */
+static union lp_build_flow_construct_data *
+lp_build_flow_push(struct lp_build_flow_context *flow,
+ enum lp_build_flow_construct_kind kind)
+{
+ assert(flow->num_constructs < LP_BUILD_FLOW_MAX_DEPTH);
+ if(flow->num_constructs >= LP_BUILD_FLOW_MAX_DEPTH)
+ return NULL;
+
+ flow->constructs[flow->num_constructs].kind = kind;
+ return &flow->constructs[flow->num_constructs++].data;
}
+/**
+ * Return the current/top flow control construct on the stack.
+ * \param kind the expected type of the top-most construct
+ */
+static union lp_build_flow_construct_data *
+lp_build_flow_peek(struct lp_build_flow_context *flow,
+ enum lp_build_flow_construct_kind kind)
+{
+ assert(flow->num_constructs);
+ if(!flow->num_constructs)
+ return NULL;
+
+ assert(flow->constructs[flow->num_constructs - 1].kind == kind);
+ if(flow->constructs[flow->num_constructs - 1].kind != kind)
+ return NULL;
+
+ return &flow->constructs[flow->num_constructs - 1].data;
+}
+
+
+/**
+ * End/pop the current/top flow control construct on the stack.
+ * \param kind the expected type of the top-most construct
+ */
+static union lp_build_flow_construct_data *
+lp_build_flow_pop(struct lp_build_flow_context *flow,
+ enum lp_build_flow_construct_kind kind)
+{
+ assert(flow->num_constructs);
+ if(!flow->num_constructs)
+ return NULL;
+
+ assert(flow->constructs[flow->num_constructs - 1].kind == kind);
+ if(flow->constructs[flow->num_constructs - 1].kind != kind)
+ return NULL;
+
+ return &flow->constructs[--flow->num_constructs].data;
+}
+
+
+/**
+ * Begin a variable scope.
+ *
+ *
+ */
void
-lp_build_mask_update(struct lp_build_mask_context *mask,
- LLVMValueRef value)
+lp_build_flow_scope_begin(struct lp_build_flow_context *flow)
{
+ struct lp_build_flow_scope *scope;
- LLVMValueRef cond;
- LLVMBasicBlockRef current_block;
- LLVMBasicBlockRef next_block;
- LLVMBasicBlockRef new_block;
+ scope = &lp_build_flow_push(flow, LP_BUILD_FLOW_SCOPE)->scope;
+ if(!scope)
+ return;
- if(mask->value)
- mask->value = LLVMBuildAnd(mask->builder, mask->value, value, "");
- else
- mask->value = value;
+ scope->num_variables = 0;
+}
- /* FIXME: disabled until we have proper control flow helpers */
-#if 0
- cond = LLVMBuildICmp(mask->builder,
- LLVMIntEQ,
- LLVMBuildBitCast(mask->builder, mask->value, mask->reg_type, ""),
- LLVMConstNull(mask->reg_type),
- "");
- current_block = LLVMGetInsertBlock(mask->builder);
+/**
+ * Declare a variable.
+ *
+ * A variable is a named entity which can have different LLVMValueRef's at
+ * different points of the program. This is relevant for control flow because
+ * when there are multiple branches to a same location we need to replace
+ * the variable's value with a Phi function as explained in
+ * http://en.wikipedia.org/wiki/Static_single_assignment_form .
+ *
+ * We keep track of variables by keeping around a pointer to where they're
+ * current.
+ *
+ * There are a few cautions to observe:
+ *
+ * - Variable's value must not be NULL. If there is no initial value then
+ * LLVMGetUndef() should be used.
+ *
+ * - Variable's value must be kept up-to-date. If the variable is going to be
+ * modified by a function then a pointer should be passed so that its value
+ * is accurate. Failure to do this will cause some of the variables'
+ * transient values to be lost, leading to wrong results.
+ *
+ * - A program should be written from top to bottom, by always appending
+ * instructions to the bottom with a single LLVMBuilderRef. Inserting and/or
+ * modifying existing statements will most likely lead to wrong results.
+ *
+ */
+void
+lp_build_flow_scope_declare(struct lp_build_flow_context *flow,
+ LLVMValueRef *variable)
+{
+ struct lp_build_flow_scope *scope;
+
+ scope = &lp_build_flow_peek(flow, LP_BUILD_FLOW_SCOPE)->scope;
+ if(!scope)
+ return;
- if(!mask->skip_block) {
- LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
- mask->skip_block = LLVMAppendBasicBlock(function, "skip");
+ assert(*variable);
+ if(!*variable)
+ return;
- mask->phi = LLVMBuildPhi(mask->builder, LLVMTypeOf(mask->value), "");
+ assert(flow->num_variables < LP_BUILD_FLOW_MAX_VARIABLES);
+ if(flow->num_variables >= LP_BUILD_FLOW_MAX_VARIABLES)
+ return;
+
+ flow->variables[flow->num_variables++] = variable;
+ ++scope->num_variables;
+}
+
+
+void
+lp_build_flow_scope_end(struct lp_build_flow_context *flow)
+{
+ struct lp_build_flow_scope *scope;
+
+ scope = &lp_build_flow_pop(flow, LP_BUILD_FLOW_SCOPE)->scope;
+ if(!scope)
+ return;
+
+ assert(flow->num_variables >= scope->num_variables);
+ if(flow->num_variables < scope->num_variables) {
+ flow->num_variables = 0;
+ return;
}
+ flow->num_variables -= scope->num_variables;
+}
+
+
+/**
+ * Note: this function has no dependencies on the flow code and could
+ * be used elsewhere.
+ */
+static LLVMBasicBlockRef
+lp_build_insert_new_block(LLVMBuilderRef builder, const char *name)
+{
+ LLVMBasicBlockRef current_block;
+ LLVMBasicBlockRef next_block;
+ LLVMBasicBlockRef new_block;
+
+ /* get current basic block */
+ current_block = LLVMGetInsertBlock(builder);
+
+ /* check if there's another block after this one */
next_block = LLVMGetNextBasicBlock(current_block);
- assert(next_block);
- if(next_block) {
- new_block = LLVMInsertBasicBlock(next_block, "");
+ if (next_block) {
+ /* insert the new block before the next block */
+ new_block = LLVMInsertBasicBlock(next_block, name);
}
else {
+ /* append new block after current block */
LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
- new_block = LLVMAppendBasicBlock(function, "");
+ new_block = LLVMAppendBasicBlock(function, name);
}
- LLVMAddIncoming(mask->phi, &mask->value, ¤t_block, 1);
- LLVMBuildCondBr(mask->builder, cond, mask->skip_block, new_block);
+ return new_block;
+}
+
- LLVMPositionBuilderAtEnd(mask->builder, new_block);
-#endif
+static LLVMBasicBlockRef
+lp_build_flow_insert_block(struct lp_build_flow_context *flow)
+{
+ return lp_build_insert_new_block(flow->builder, "");
}
-LLVMValueRef
-lp_build_mask_end(struct lp_build_mask_context *mask)
+/**
+ * Begin a "skip" block. Inside this block we can test a condition and
+ * skip to the end of the block if the condition is false.
+ */
+void
+lp_build_flow_skip_begin(struct lp_build_flow_context *flow)
{
- if(mask->skip_block) {
- LLVMBasicBlockRef current_block = LLVMGetInsertBlock(mask->builder);
+ struct lp_build_flow_skip *skip;
+ LLVMBuilderRef builder;
+ unsigned i;
+
+ skip = &lp_build_flow_push(flow, LP_BUILD_FLOW_SKIP)->skip;
+ if(!skip)
+ return;
- LLVMAddIncoming(mask->phi, &mask->value, ¤t_block, 1);
- LLVMBuildBr(mask->builder, mask->skip_block);
+ /* create new basic block */
+ skip->block = lp_build_flow_insert_block(flow);
- LLVMPositionBuilderAtEnd(mask->builder, mask->skip_block);
+ skip->num_variables = flow->num_variables;
+ if(!skip->num_variables) {
+ skip->phi = NULL;
+ return;
+ }
- mask->value = mask->phi;
- mask->phi = NULL;
- mask->skip_block = NULL;
+ /* Allocate a Phi node for each variable in this skip scope */
+ skip->phi = MALLOC(skip->num_variables * sizeof *skip->phi);
+ if(!skip->phi) {
+ skip->num_variables = 0;
+ return;
}
+ builder = LLVMCreateBuilder();
+ LLVMPositionBuilderAtEnd(builder, skip->block);
+
+ /* create a Phi node for each variable */
+ for(i = 0; i < skip->num_variables; ++i)
+ skip->phi[i] = LLVMBuildPhi(builder, LLVMTypeOf(*flow->variables[i]), "");
+
+ LLVMDisposeBuilder(builder);
+}
+
+
+/**
+ * Insert code to test a condition and branch to the end of the current
+ * skip block if the condition is true.
+ */
+void
+lp_build_flow_skip_cond_break(struct lp_build_flow_context *flow,
+ LLVMValueRef cond)
+{
+ struct lp_build_flow_skip *skip;
+ LLVMBasicBlockRef current_block;
+ LLVMBasicBlockRef new_block;
+ unsigned i;
+
+ skip = &lp_build_flow_peek(flow, LP_BUILD_FLOW_SKIP)->skip;
+ if(!skip)
+ return;
+
+ current_block = LLVMGetInsertBlock(flow->builder);
+
+ new_block = lp_build_flow_insert_block(flow);
+
+ /* for each variable, update the Phi node with a (variable, block) pair */
+ for(i = 0; i < skip->num_variables; ++i) {
+ assert(*flow->variables[i]);
+ LLVMAddIncoming(skip->phi[i], flow->variables[i], ¤t_block, 1);
+ }
+
+ /* if cond is true, goto skip->block, else goto new_block */
+ LLVMBuildCondBr(flow->builder, cond, skip->block, new_block);
+
+ LLVMPositionBuilderAtEnd(flow->builder, new_block);
+}
+
+
+void
+lp_build_flow_skip_end(struct lp_build_flow_context *flow)
+{
+ struct lp_build_flow_skip *skip;
+ LLVMBasicBlockRef current_block;
+ unsigned i;
+
+ skip = &lp_build_flow_pop(flow, LP_BUILD_FLOW_SKIP)->skip;
+ if(!skip)
+ return;
+
+ current_block = LLVMGetInsertBlock(flow->builder);
+
+ /* add (variable, block) tuples to the phi nodes */
+ for(i = 0; i < skip->num_variables; ++i) {
+ assert(*flow->variables[i]);
+ LLVMAddIncoming(skip->phi[i], flow->variables[i], ¤t_block, 1);
+ *flow->variables[i] = skip->phi[i];
+ }
+
+ /* goto block */
+ LLVMBuildBr(flow->builder, skip->block);
+ LLVMPositionBuilderAtEnd(flow->builder, skip->block);
+
+ FREE(skip->phi);
+}
+
+
+/**
+ * Check if the mask predicate is zero. If so, jump to the end of the block.
+ */
+static void
+lp_build_mask_check(struct lp_build_mask_context *mask)
+{
+ LLVMBuilderRef builder = mask->flow->builder;
+ LLVMValueRef cond;
+
+ /* cond = (mask == 0) */
+ cond = LLVMBuildICmp(builder,
+ LLVMIntEQ,
+ LLVMBuildBitCast(builder, mask->value, mask->reg_type, ""),
+ LLVMConstNull(mask->reg_type),
+ "");
+
+ /* if cond, goto end of block */
+ lp_build_flow_skip_cond_break(mask->flow, cond);
+}
+
+
+/**
+ * Begin a section of code which is predicated on a mask.
+ * \param mask the mask context, initialized here
+ * \param flow the flow context
+ * \param type the type of the mask
+ * \param value storage for the mask
+ */
+void
+lp_build_mask_begin(struct lp_build_mask_context *mask,
+ struct lp_build_flow_context *flow,
+ struct lp_type type,
+ LLVMValueRef value)
+{
+ memset(mask, 0, sizeof *mask);
+
+ mask->flow = flow;
+ mask->reg_type = LLVMIntType(type.width * type.length);
+ mask->value = value;
+
+ lp_build_flow_scope_begin(flow);
+ lp_build_flow_scope_declare(flow, &mask->value);
+ lp_build_flow_skip_begin(flow);
+
+ lp_build_mask_check(mask);
+}
+
+
+/**
+ * Update boolean mask with given value (bitwise AND).
+ * Typically used to update the quad's pixel alive/killed mask
+ * after depth testing, alpha testing, TGSI_OPCODE_KIL, etc.
+ */
+void
+lp_build_mask_update(struct lp_build_mask_context *mask,
+ LLVMValueRef value)
+{
+ mask->value = LLVMBuildAnd( mask->flow->builder, mask->value, value, "");
+
+ lp_build_mask_check(mask);
+}
+
+
+/**
+ * End section of code which is predicated on a mask.
+ */
+LLVMValueRef
+lp_build_mask_end(struct lp_build_mask_context *mask)
+{
+ lp_build_flow_skip_end(mask->flow);
+ lp_build_flow_scope_end(mask->flow);
return mask->value;
}
LLVMPositionBuilderAtEnd(builder, after_block);
}
+
+
+/*
+ Example of if/then/else building:
+
+ int x;
+ if (cond) {
+ x = 1 + 2;
+ }
+ else {
+ x = 2 + 3;
+ }
+
+ Is built with:
+
+ LLVMValueRef x = LLVMGetUndef(); // or something else
+
+ flow = lp_build_flow_create(builder);
+
+ lp_build_flow_scope_begin(flow);
+
+ // x needs a phi node
+ lp_build_flow_scope_declare(flow, &x);
+
+ lp_build_if(ctx, flow, builder, cond);
+ x = LLVMAdd(1, 2);
+ lp_build_else(ctx);
+ x = LLVMAdd(2, 3);
+ lp_build_endif(ctx);
+
+ lp_build_flow_scope_end(flow);
+
+ lp_build_flow_destroy(flow);
+ */
+
+
+
+/**
+ * Begin an if/else/endif construct.
+ */
+void
+lp_build_if(struct lp_build_if_state *ctx,
+ struct lp_build_flow_context *flow,
+ LLVMBuilderRef builder,
+ LLVMValueRef condition)
+{
+ LLVMBasicBlockRef block = LLVMGetInsertBlock(builder);
+ struct lp_build_flow_if *ifthen;
+ unsigned i;
+
+ memset(ctx, 0, sizeof(*ctx));
+ ctx->builder = builder;
+ ctx->flow = flow;
+
+ /* push/create new scope */
+ ifthen = &lp_build_flow_push(flow, LP_BUILD_FLOW_IF)->ifthen;
+ assert(ifthen);
+
+ ifthen->num_variables = flow->num_variables;
+ ifthen->condition = condition;
+ ifthen->entry_block = block;
+
+ /* create a Phi node for each variable in this flow scope */
+ ifthen->phi = MALLOC(ifthen->num_variables * sizeof(*ifthen->phi));
+ if (!ifthen->phi) {
+ ifthen->num_variables = 0;
+ return;
+ }
+
+ /* create endif/merge basic block for the phi functions */
+ ifthen->merge_block = lp_build_insert_new_block(builder, "endif-block");
+ LLVMPositionBuilderAtEnd(builder, ifthen->merge_block);
+
+ /* create a phi node for each variable */
+ for (i = 0; i < flow->num_variables; i++) {
+ ifthen->phi[i] = LLVMBuildPhi(builder, LLVMTypeOf(*flow->variables[i]), "");
+
+ /* add add the initial value of the var from the entry block */
+ LLVMAddIncoming(ifthen->phi[i], flow->variables[i], &ifthen->entry_block, 1);
+ }
+
+ /* create/insert true_block before merge_block */
+ ifthen->true_block = LLVMInsertBasicBlock(ifthen->merge_block, "if-true-block");
+
+ /* successive code goes into the true block */
+ LLVMPositionBuilderAtEnd(builder, ifthen->true_block);
+}
+
+
+/**
+ * Begin else-part of a conditional
+ */
+void
+lp_build_else(struct lp_build_if_state *ctx)
+{
+ struct lp_build_flow_context *flow = ctx->flow;
+ struct lp_build_flow_if *ifthen;
+ unsigned i;
+
+ ifthen = &lp_build_flow_peek(flow, LP_BUILD_FLOW_IF)->ifthen;
+ assert(ifthen);
+
+ /* for each variable, update the Phi node with a (variable, block) pair */
+ LLVMPositionBuilderAtEnd(ctx->builder, ifthen->merge_block);
+ for (i = 0; i < flow->num_variables; i++) {
+ assert(*flow->variables[i]);
+ LLVMAddIncoming(ifthen->phi[i], flow->variables[i], &ifthen->true_block, 1);
+ }
+
+ /* create/insert false_block before the merge block */
+ ifthen->false_block = LLVMInsertBasicBlock(ifthen->merge_block, "if-false-block");
+
+ /* successive code goes into the else block */
+ LLVMPositionBuilderAtEnd(ctx->builder, ifthen->false_block);
+}
+
+
+/**
+ * End a conditional.
+ */
+void
+lp_build_endif(struct lp_build_if_state *ctx)
+{
+ struct lp_build_flow_context *flow = ctx->flow;
+ struct lp_build_flow_if *ifthen;
+ unsigned i;
+
+ ifthen = &lp_build_flow_pop(flow, LP_BUILD_FLOW_IF)->ifthen;
+ assert(ifthen);
+
+ if (ifthen->false_block) {
+ LLVMPositionBuilderAtEnd(ctx->builder, ifthen->merge_block);
+ /* for each variable, update the Phi node with a (variable, block) pair */
+ for (i = 0; i < flow->num_variables; i++) {
+ assert(*flow->variables[i]);
+ LLVMAddIncoming(ifthen->phi[i], flow->variables[i], &ifthen->false_block, 1);
+
+ /* replace the variable ref with the phi function */
+ *flow->variables[i] = ifthen->phi[i];
+ }
+ }
+ else {
+ /* no else clause */
+ LLVMPositionBuilderAtEnd(ctx->builder, ifthen->merge_block);
+ for (i = 0; i < flow->num_variables; i++) {
+ assert(*flow->variables[i]);
+ LLVMAddIncoming(ifthen->phi[i], flow->variables[i], &ifthen->true_block, 1);
+
+ /* replace the variable ref with the phi function */
+ *flow->variables[i] = ifthen->phi[i];
+ }
+ }
+
+ FREE(ifthen->phi);
+
+ /***
+ *** Now patch in the various branch instructions.
+ ***/
+
+ /* Insert the conditional branch instruction at the end of entry_block */
+ LLVMPositionBuilderAtEnd(ctx->builder, ifthen->entry_block);
+ if (ifthen->false_block) {
+ /* we have an else clause */
+ LLVMBuildCondBr(ctx->builder, ifthen->condition,
+ ifthen->true_block, ifthen->false_block);
+ }
+ else {
+ /* no else clause */
+ LLVMBuildCondBr(ctx->builder, ifthen->condition,
+ ifthen->true_block, ifthen->merge_block);
+ }
+
+ /* Append an unconditional Br(anch) instruction on the true_block */
+ LLVMPositionBuilderAtEnd(ctx->builder, ifthen->true_block);
+ LLVMBuildBr(ctx->builder, ifthen->merge_block);
+ if (ifthen->false_block) {
+ /* Append an unconditional Br(anch) instruction on the false_block */
+ LLVMPositionBuilderAtEnd(ctx->builder, ifthen->false_block);
+ LLVMBuildBr(ctx->builder, ifthen->merge_block);
+ }
+
+
+ /* Resume building code at end of the ifthen->merge_block */
+ LLVMPositionBuilderAtEnd(ctx->builder, ifthen->merge_block);
+}
projects / mesa.git / blobdiff