diff options
Diffstat (limited to 'src/gallium/drivers/llvmpipe/lp_bld_flow.c')
-rw-r--r-- | src/gallium/drivers/llvmpipe/lp_bld_flow.c | 308 |
1 files changed, 299 insertions, 9 deletions
diff --git a/src/gallium/drivers/llvmpipe/lp_bld_flow.c b/src/gallium/drivers/llvmpipe/lp_bld_flow.c index 25c10af29f..230edc6a5c 100644 --- a/src/gallium/drivers/llvmpipe/lp_bld_flow.c +++ b/src/gallium/drivers/llvmpipe/lp_bld_flow.c @@ -41,13 +41,16 @@ #define LP_BUILD_FLOW_MAX_VARIABLES 32 #define LP_BUILD_FLOW_MAX_DEPTH 32 +#define LP_BUILD_IF_MAX_VARIABLES 8 + /** * Enumeration of all possible flow constructs. */ enum lp_build_flow_construct_kind { - lP_BUILD_FLOW_SCOPE, - LP_BUILD_FLOW_SKIP + LP_BUILD_FLOW_SCOPE, + LP_BUILD_FLOW_SKIP, + LP_BUILD_FLOW_IF }; @@ -73,7 +76,24 @@ struct lp_build_flow_skip /** Number of variables declared at the beginning */ unsigned num_variables; - LLVMValueRef *phi; + LLVMValueRef *phi; /**< array [num_variables] */ +}; + + +/** + * if/else/endif. + */ +struct lp_build_flow_if +{ + unsigned num_variables; + + /** phi variables in the true clause */ + LLVMValueRef true_variables[LP_BUILD_IF_MAX_VARIABLES]; + unsigned num_true_variables; + + /** phi variables in the false clause */ + LLVMValueRef false_variables[LP_BUILD_IF_MAX_VARIABLES]; + unsigned num_false_variables; }; @@ -84,6 +104,7 @@ union lp_build_flow_construct_data { struct lp_build_flow_scope scope; struct lp_build_flow_skip skip; + struct lp_build_flow_if ifthen; }; @@ -145,6 +166,10 @@ lp_build_flow_destroy(struct lp_build_flow_context *flow) } +/** + * 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) @@ -158,6 +183,10 @@ lp_build_flow_push(struct lp_build_flow_context *flow, } +/** + * 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) @@ -174,6 +203,10 @@ lp_build_flow_peek(struct lp_build_flow_context *flow, } +/** + * 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) @@ -200,7 +233,7 @@ lp_build_flow_scope_begin(struct lp_build_flow_context *flow) { struct lp_build_flow_scope *scope; - scope = &lp_build_flow_push(flow, lP_BUILD_FLOW_SCOPE)->scope; + scope = &lp_build_flow_push(flow, LP_BUILD_FLOW_SCOPE)->scope; if(!scope) return; @@ -213,11 +246,11 @@ lp_build_flow_scope_begin(struct lp_build_flow_context *flow) * * 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 mutiple branches to a same location we need to replace + * 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 their + * We keep track of variables by keeping around a pointer to where they're * current. * * There are a few cautions to observe: @@ -241,7 +274,7 @@ lp_build_flow_scope_declare(struct lp_build_flow_context *flow, { struct lp_build_flow_scope *scope; - scope = &lp_build_flow_peek(flow, lP_BUILD_FLOW_SCOPE)->scope; + scope = &lp_build_flow_peek(flow, LP_BUILD_FLOW_SCOPE)->scope; if(!scope) return; @@ -263,7 +296,7 @@ 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; + scope = &lp_build_flow_pop(flow, LP_BUILD_FLOW_SCOPE)->scope; if(!scope) return; @@ -298,6 +331,11 @@ lp_build_flow_insert_block(struct lp_build_flow_context *flow) return new_block; } + +/** + * 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) { @@ -309,13 +347,16 @@ lp_build_flow_skip_begin(struct lp_build_flow_context *flow) if(!skip) return; + /* create new basic block */ skip->block = lp_build_flow_insert_block(flow); + skip->num_variables = flow->num_variables; if(!skip->num_variables) { skip->phi = NULL; return; } + /* 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; @@ -325,6 +366,7 @@ lp_build_flow_skip_begin(struct lp_build_flow_context *flow) 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]), ""); @@ -332,6 +374,10 @@ lp_build_flow_skip_begin(struct lp_build_flow_context *flow) } +/** + * 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) @@ -349,15 +395,17 @@ lp_build_flow_skip_cond_break(struct lp_build_flow_context *flow, 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 @@ -373,12 +421,14 @@ lp_build_flow_skip_end(struct lp_build_flow_context *flow) 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); @@ -386,22 +436,34 @@ lp_build_flow_skip_end(struct lp_build_flow_context *flow) } +/** + * 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, @@ -422,6 +484,11 @@ lp_build_mask_begin(struct lp_build_mask_context *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) @@ -432,6 +499,9 @@ lp_build_mask_update(struct lp_build_mask_context *mask, } +/** + * End section of code which is predicated on a mask. + */ LLVMValueRef lp_build_mask_end(struct lp_build_mask_context *mask) { @@ -491,3 +561,223 @@ lp_build_loop_end(LLVMBuilderRef builder, LLVMPositionBuilderAtEnd(builder, after_block); } + + +/* + Example of if/then/else building: + + int x; + if (cond) { + x = 1 + 2; + } + else { + x = 2 + 3; + } + + Is built with: + + flow = lp_build_flow_create(builder); + ... + + lp_build_flow_scope_declare(flow, "x"); + + lp_build_if(ctx, flow, builder, cond); + x = LLVMAdd(1, 2); + lp_build_if_phi_var(ctx, "x"); + lp_build_else(ctx); + x = LLVMAdd(2, 3); + lp_build_if_phi_var(ctx, "x"); + lp_build_endif(ctx); + + ... + + flow = lp_build_flow_end(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); + LLVMValueRef function = LLVMGetBasicBlockParent(block); + struct lp_build_flow_if *ifthen; + + memset(ctx, 0, sizeof(*ctx)); + ctx->builder = builder; + ctx->flow = flow; + ctx->condition = condition; + ctx->entry_block = block; + + /* push/create new scope */ + ifthen = &lp_build_flow_push(flow, LP_BUILD_FLOW_IF)->ifthen; + assert(ifthen); + + ifthen->num_variables = flow->num_variables; + ifthen->num_true_variables = 0; + ifthen->num_false_variables = 0; + + /* allocate the block for the if/true clause */ + ctx->true_block = LLVMAppendBasicBlock(function, "true block"); + /* XXX is this correct ??? */ + LLVMPositionBuilderAtEnd(builder, ctx->true_block); +} + + +/** + * Begin else-part of a conditional + */ +void +lp_build_else(struct lp_build_if_state *ctx) +{ + LLVMBasicBlockRef block = LLVMGetInsertBlock(ctx->builder); + LLVMValueRef function = LLVMGetBasicBlockParent(block); + struct lp_build_flow_if *ifthen; + + ifthen = &lp_build_flow_peek(ctx->flow, LP_BUILD_FLOW_IF)->ifthen; + assert(ifthen); + + /* allocate the block for the else/false clause */ + ctx->false_block = LLVMAppendBasicBlock(function, "false block"); + /* XXX is this correct ??? */ + LLVMPositionBuilderAtEnd(ctx->builder, ctx->false_block); +} + + +/** + * End a conditional. + * This involves building a "merge" block at the endif which + * contains the phi instructions. + */ +void +lp_build_endif(struct lp_build_if_state *ctx) +{ + LLVMBasicBlockRef block = LLVMGetInsertBlock(ctx->builder); + LLVMValueRef function = LLVMGetBasicBlockParent(block); + LLVMBasicBlockRef merge_block = LLVMAppendBasicBlock(function, "endif block"); + LLVMValueRef phi[LP_BUILD_FLOW_MAX_VARIABLES]; + struct lp_build_flow_if *ifthen; + unsigned i; + + /* build the endif/merge block now */ + /* XXX this is probably wrong */ + LLVMPositionBuilderAtEnd(ctx->builder, merge_block); + + ifthen = &lp_build_flow_pop(ctx->flow, LP_BUILD_FLOW_IF)->ifthen; + assert(ifthen); + + memset(phi, 0, sizeof(phi)); + + /* build phi nodes for any variables which were declared inside if part */ + + for (i = 0; i < ifthen->num_variables; i++) { + LLVMValueRef *var = ctx->flow->variables[i]; + const char *name = LLVMGetValueName(*var); + unsigned j; + + /* search true-clause variables list for 'name' */ + for (j = 0; j < ifthen->num_true_variables; j++) { + LLVMValueRef v = ifthen->true_variables[j]; + if (strcmp(LLVMGetValueName(v), name) == 0) { + /* add phi */ + if (!phi[i]) + phi[i] = LLVMBuildPhi(ctx->builder, LLVMTypeOf(*var), ""); + LLVMAddIncoming(phi[i], &v, &ctx->true_block, 1); + } + } + + /* search false-clause variables list for 'name' */ + for (j = 0; j < ifthen->num_false_variables; j++) { + LLVMValueRef v = ifthen->false_variables[j]; + if (strcmp(LLVMGetValueName(v), name) == 0) { + /* add phi */ + if (!phi[i]) + phi[i] = LLVMBuildPhi(ctx->builder, LLVMTypeOf(*var), ""); + LLVMAddIncoming(phi[i], &v, &ctx->false_block, 1); + } + } + + /* "return" new phi variable to calling code */ + if (phi[i]) + *var = phi[i]; + } + + /*** + *** Insert the various branch instructions here. + *** XXX need to verify all the builder/block positioning is correct. + ***/ + + /* Insert the conditional branch instruction at the end of entry_block */ + LLVMPositionBuilderAtEnd(ctx->builder, ctx->entry_block); + + if (ctx->false_block) { + /* we have an else clause */ + LLVMBuildCondBr(ctx->builder, ctx->condition, + ctx->true_block, ctx->false_block); + } + else { + /* no else clause */ + LLVMBuildCondBr(ctx->builder, ctx->condition, + ctx->true_block, merge_block); + } + + /* Append an unconditional Br(anch) instruction on the true_block */ + LLVMPositionBuilderAtEnd(ctx->builder, ctx->true_block); + LLVMBuildBr(ctx->builder, merge_block); + if (ctx->false_block) { + /* Append an unconditional Br(anch) instruction on the false_block */ + LLVMPositionBuilderAtEnd(ctx->builder, ctx->false_block); + LLVMBuildBr(ctx->builder, merge_block); + } + + + /* Finish-up: continue building at end of the merge_block */ + /* XXX is this right? */ + LLVMPositionBuilderAtEnd(ctx->builder, merge_block); +} + + +/** + * Declare a variable that needs to be merged with another variable + * via a phi function. + * This function must be called after lp_build_if() and lp_build_endif(). + */ +void +lp_build_if_phi_var(struct lp_build_if_state *ctx, LLVMValueRef var) +{ + struct lp_build_flow_if *ifthen; + const char *name; + + name = LLVMGetValueName(var); + assert(name && "variable requires a name"); + + /* make sure the var existed before the if/then/else */ + { + boolean found = FALSE; + uint i; + for (i = 0; i < ctx->flow->num_variables; i++) { + LLVMValueRef *var = ctx->flow->variables[i]; + if (strcmp(LLVMGetValueName(*var), name) == 0) { + found = TRUE; + break; + } + } + assert(found); + } + + ifthen = &lp_build_flow_pop(ctx->flow, LP_BUILD_FLOW_IF)->ifthen; + + if (ctx->false_block) { + ifthen->false_variables[ifthen->num_false_variables++] = var; + } + else { + assert(ctx->true_block); + ifthen->true_variables[ifthen->num_true_variables++] = var; + } +} |