/************************************************************************** * * 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 64 #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. */ 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]); assert(LLVMTypeOf(skip->phi[i]) == LLVMTypeOf(*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]); assert(LLVMTypeOf(skip->phi[i]) == LLVMTypeOf(*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. */ void lp_build_mask_check(struct lp_build_mask_context *mask) { LLVMBuilderRef builder = mask->flow->builder; LLVMValueRef value; LLVMValueRef cond; value = lp_build_mask_value(mask); /* cond = (mask == 0) */ cond = LLVMBuildICmp(builder, LLVMIntEQ, LLVMBuildBitCast(builder, 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->var = lp_build_alloca(flow->builder, lp_build_int_vec_type(type), "execution_mask"); LLVMBuildStore(flow->builder, value, mask->var); lp_build_flow_skip_begin(flow); } LLVMValueRef lp_build_mask_value(struct lp_build_mask_context *mask) { return LLVMBuildLoad(mask->flow->builder, mask->var, ""); } /** * 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) { value = LLVMBuildAnd(mask->flow->builder, lp_build_mask_value(mask), value, ""); LLVMBuildStore(mask->flow->builder, value, mask->var); } /** * 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); return lp_build_mask_value(mask); } 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); } void lp_build_loop_end_cond(LLVMBuilderRef builder, LLVMValueRef end, LLVMValueRef step, int llvm_cond, 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, llvm_cond, 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 */ if (!LLVMIsUndef(*flow->variables[i])) 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; LLVMBasicBlockRef curBlock = LLVMGetInsertBlock(ctx->builder); unsigned i; ifthen = &lp_build_flow_pop(flow, LP_BUILD_FLOW_IF)->ifthen; assert(ifthen); /* Insert branch to the merge block from current block */ LLVMBuildBr(ctx->builder, ifthen->merge_block); 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], &curBlock, 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); } /* Insert branch from end of true_block to merge_block */ if (ifthen->false_block) { /* Append an unconditional Br(anch) instruction on the true_block */ LLVMPositionBuilderAtEnd(ctx->builder, ifthen->true_block); LLVMBuildBr(ctx->builder, ifthen->merge_block); } else { /* No else clause. * Note that we've already inserted the branch at the end of * true_block. See the very first LLVMBuildBr() call in this function. */ } /* Resume building code at end of the ifthen->merge_block */ LLVMPositionBuilderAtEnd(ctx->builder, ifthen->merge_block); } /** * Allocate a scalar (or vector) variable. * * Although not strictly part of control flow, control flow has deep impact in * how variables should be allocated. * * The mem2reg optimization pass is the recommended way to dealing with mutable * variables, and SSA. It looks for allocas and if it can handle them, it * promotes them, but only looks for alloca instructions in the entry block of * the function. Being in the entry block guarantees that the alloca is only * executed once, which makes analysis simpler. * * See also: * - http://www.llvm.org/docs/tutorial/OCamlLangImpl7.html#memory */ LLVMValueRef lp_build_alloca(LLVMBuilderRef builder, LLVMTypeRef type, const char *name) { LLVMBasicBlockRef current_block = LLVMGetInsertBlock(builder); LLVMValueRef function = LLVMGetBasicBlockParent(current_block); LLVMBasicBlockRef first_block = LLVMGetEntryBasicBlock(function); LLVMValueRef first_instr = LLVMGetFirstInstruction(first_block); LLVMBuilderRef first_builder = LLVMCreateBuilder(); LLVMValueRef res; if (first_instr) { LLVMPositionBuilderBefore(first_builder, first_instr); } else { LLVMPositionBuilderAtEnd(first_builder, first_block); } res = LLVMBuildAlloca(first_builder, type, name); LLVMBuildStore(builder, LLVMConstNull(type), res); LLVMDisposeBuilder(first_builder); return res; } /** * Allocate an array of scalars/vectors. * * mem2reg pass is not capable of promoting structs or arrays to registers, but * we still put it in the first block anyway as failure to put allocas in the * first block may prevent the X86 backend from successfully align the stack as * required. * * Also the scalarrepl pass is supposedly more powerful and can promote * arrays in many cases. * * See also: * - http://www.llvm.org/docs/tutorial/OCamlLangImpl7.html#memory */ LLVMValueRef lp_build_array_alloca(LLVMBuilderRef builder, LLVMTypeRef type, LLVMValueRef count, const char *name) { LLVMBasicBlockRef current_block = LLVMGetInsertBlock(builder); LLVMValueRef function = LLVMGetBasicBlockParent(current_block); LLVMBasicBlockRef first_block = LLVMGetEntryBasicBlock(function); LLVMValueRef first_instr = LLVMGetFirstInstruction(first_block); LLVMBuilderRef first_builder = LLVMCreateBuilder(); LLVMValueRef res; if (first_instr) { LLVMPositionBuilderBefore(first_builder, first_instr); } else { LLVMPositionBuilderAtEnd(first_builder, first_block); } res = LLVMBuildArrayAlloca(first_builder, type, count, name); LLVMDisposeBuilder(first_builder); return res; }