/************************************************************************** * * 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 */ #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 #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_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; /** 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; }; /** * 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; } static LLVMBasicBlockRef lp_build_flow_insert_block(struct lp_build_flow_context *flow) { LLVMBasicBlockRef current_block; LLVMBasicBlockRef next_block; LLVMBasicBlockRef new_block; current_block = LLVMGetInsertBlock(flow->builder); next_block = LLVMGetNextBasicBlock(current_block); if(next_block) { new_block = LLVMInsertBasicBlock(next_block, ""); } else { LLVMValueRef function = LLVMGetBasicBlockParent(current_block); new_block = LLVMAppendBasicBlock(function, ""); } 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) { 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: 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; } }