diff options
Diffstat (limited to 'src/gallium/auxiliary/gallivm/lp_bld_flow.c')
| -rw-r--r-- | src/gallium/auxiliary/gallivm/lp_bld_flow.c | 757 |
1 files changed, 757 insertions, 0 deletions
diff --git a/src/gallium/auxiliary/gallivm/lp_bld_flow.c b/src/gallium/auxiliary/gallivm/lp_bld_flow.c new file mode 100644 index 00000000000..bc831389085 --- /dev/null +++ b/src/gallium/auxiliary/gallivm/lp_bld_flow.c @@ -0,0 +1,757 @@ +/************************************************************************** + * + * Copyright 2009 VMware, Inc. + * All Rights Reserved. + * + * 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 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 VMWARE AND/OR ITS 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. + * + **************************************************************************/ + +/** + * LLVM control flow build helpers. + * + * @author Jose Fonseca <jfonseca@vmware.com> + */ + +#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_flow_destroy(struct lp_build_flow_context *flow) +{ + assert(flow->num_constructs == 0); + assert(flow->num_variables == 0); + FREE(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) +{ + 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_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; + if(!scope) + return; + + scope->num_variables = 0; +} + + +/** + * 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; + + assert(*variable); + if(!*variable) + return; + + 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); + 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, name); + } + + return new_block; +} + + +static LLVMBasicBlockRef +lp_build_flow_insert_block(struct lp_build_flow_context *flow) +{ + return lp_build_insert_new_block(flow->builder, ""); +} + + +/** + * 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) +{ + struct lp_build_flow_skip *skip; + LLVMBuilderRef builder; + unsigned i; + + skip = &lp_build_flow_push(flow, LP_BUILD_FLOW_SKIP)->skip; + 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; + 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; +} + + + +void +lp_build_loop_begin(LLVMBuilderRef builder, + LLVMValueRef start, + struct lp_build_loop_state *state) +{ + LLVMBasicBlockRef block = LLVMGetInsertBlock(builder); + LLVMValueRef function = LLVMGetBasicBlockParent(block); + + state->block = LLVMAppendBasicBlock(function, "loop"); + + LLVMBuildBr(builder, state->block); + + LLVMPositionBuilderAtEnd(builder, state->block); + + state->counter = LLVMBuildPhi(builder, LLVMTypeOf(start), ""); + + LLVMAddIncoming(state->counter, &start, &block, 1); + +} + + +void +lp_build_loop_end(LLVMBuilderRef builder, + LLVMValueRef end, + LLVMValueRef step, + struct lp_build_loop_state *state) +{ + LLVMBasicBlockRef block = LLVMGetInsertBlock(builder); + LLVMValueRef function = LLVMGetBasicBlockParent(block); + LLVMValueRef next; + LLVMValueRef cond; + LLVMBasicBlockRef after_block; + + if (!step) + step = LLVMConstInt(LLVMTypeOf(end), 1, 0); + + next = LLVMBuildAdd(builder, state->counter, step, ""); + + cond = LLVMBuildICmp(builder, LLVMIntNE, next, end, ""); + + after_block = LLVMAppendBasicBlock(function, ""); + + LLVMBuildCondBr(builder, cond, after_block, state->block); + + LLVMAddIncoming(state->counter, &next, &block, 1); + + 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); +} |