/************************************************************************** * * 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_SKIP, LP_BUILD_FLOW_IF }; /** * 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; }; /** * if/else/endif. */ struct lp_build_flow_if { 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_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; }; 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); 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; } /** * 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; 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); builder = LLVMCreateBuilder(); LLVMPositionBuilderAtEnd(builder, skip->block); 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 new_block; skip = &lp_build_flow_peek(flow, LP_BUILD_FLOW_SKIP)->skip; if(!skip) return; new_block = lp_build_flow_insert_block(flow); /* 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; skip = &lp_build_flow_pop(flow, LP_BUILD_FLOW_SKIP)->skip; if(!skip) return; /* goto block */ LLVMBuildBr(flow->builder, skip->block); LLVMPositionBuilderAtEnd(flow->builder, skip->block); } /** * 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; 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->condition = condition; ifthen->entry_block = block; /* 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/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; ifthen = &lp_build_flow_peek(flow, LP_BUILD_FLOW_IF)->ifthen; assert(ifthen); /* 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; 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); /*** *** 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; }