/**************************************************************************
|
*
|
* 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_init.h"
|
#include "lp_bld_type.h"
|
#include "lp_bld_flow.h"
|
|
|
/**
|
* Insert a new block, right where builder is pointing to.
|
*
|
* This is useful important not only for aesthetic reasons, but also for
|
* performance reasons, as frequently run blocks should be laid out next to
|
* each other and fall-throughs maximized.
|
*
|
* See also llvm/lib/Transforms/Scalar/BasicBlockPlacement.cpp.
|
*
|
* Note: this function has no dependencies on the flow code and could
|
* be used elsewhere.
|
*/
|
LLVMBasicBlockRef
|
lp_build_insert_new_block(struct gallivm_state *gallivm, const char *name)
|
{
|
LLVMBasicBlockRef current_block;
|
LLVMBasicBlockRef next_block;
|
LLVMBasicBlockRef new_block;
|
|
/* get current basic block */
|
current_block = LLVMGetInsertBlock(gallivm->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 = LLVMInsertBasicBlockInContext(gallivm->context, next_block, name);
|
}
|
else {
|
/* append new block after current block */
|
LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
|
new_block = LLVMAppendBasicBlockInContext(gallivm->context, function, name);
|
}
|
|
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_skip_context *skip,
|
struct gallivm_state *gallivm)
|
{
|
skip->gallivm = gallivm;
|
/* create new basic block */
|
skip->block = lp_build_insert_new_block(gallivm, "skip");
|
}
|
|
|
/**
|
* 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_skip_context *skip,
|
LLVMValueRef cond)
|
{
|
LLVMBasicBlockRef new_block;
|
|
new_block = lp_build_insert_new_block(skip->gallivm, "");
|
|
/* if cond is true, goto skip->block, else goto new_block */
|
LLVMBuildCondBr(skip->gallivm->builder, cond, skip->block, new_block);
|
|
LLVMPositionBuilderAtEnd(skip->gallivm->builder, new_block);
|
}
|
|
|
void
|
lp_build_flow_skip_end(struct lp_build_skip_context *skip)
|
{
|
/* goto block */
|
LLVMBuildBr(skip->gallivm->builder, skip->block);
|
LLVMPositionBuilderAtEnd(skip->gallivm->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->skip.gallivm->builder;
|
LLVMValueRef value;
|
LLVMValueRef cond;
|
|
value = lp_build_mask_value(mask);
|
|
/*
|
* XXX this doesn't quite generate the most efficient code possible, if
|
* the masks are vectors which have all bits set to the same value
|
* in each element.
|
* movmskps/pmovmskb would be more efficient to get the required value
|
* into ordinary reg (certainly with 8 floats).
|
* Not sure if llvm could figure that out on its own.
|
*/
|
|
/* 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->skip, 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 gallivm_state *gallivm,
|
struct lp_type type,
|
LLVMValueRef value)
|
{
|
memset(mask, 0, sizeof *mask);
|
|
mask->reg_type = LLVMIntTypeInContext(gallivm->context, type.width * type.length);
|
mask->var = lp_build_alloca(gallivm,
|
lp_build_int_vec_type(gallivm, type),
|
"execution_mask");
|
|
LLVMBuildStore(gallivm->builder, value, mask->var);
|
|
lp_build_flow_skip_begin(&mask->skip, gallivm);
|
}
|
|
|
LLVMValueRef
|
lp_build_mask_value(struct lp_build_mask_context *mask)
|
{
|
return LLVMBuildLoad(mask->skip.gallivm->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_KILL_IF, etc.
|
*/
|
void
|
lp_build_mask_update(struct lp_build_mask_context *mask,
|
LLVMValueRef value)
|
{
|
value = LLVMBuildAnd(mask->skip.gallivm->builder,
|
lp_build_mask_value(mask),
|
value, "");
|
LLVMBuildStore(mask->skip.gallivm->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->skip);
|
return lp_build_mask_value(mask);
|
}
|
|
|
|
void
|
lp_build_loop_begin(struct lp_build_loop_state *state,
|
struct gallivm_state *gallivm,
|
LLVMValueRef start)
|
|
{
|
LLVMBuilderRef builder = gallivm->builder;
|
|
state->block = lp_build_insert_new_block(gallivm, "loop_begin");
|
|
state->counter_var = lp_build_alloca(gallivm, LLVMTypeOf(start), "loop_counter");
|
state->gallivm = gallivm;
|
|
LLVMBuildStore(builder, start, state->counter_var);
|
|
LLVMBuildBr(builder, state->block);
|
|
LLVMPositionBuilderAtEnd(builder, state->block);
|
|
state->counter = LLVMBuildLoad(builder, state->counter_var, "");
|
}
|
|
|
void
|
lp_build_loop_end_cond(struct lp_build_loop_state *state,
|
LLVMValueRef end,
|
LLVMValueRef step,
|
LLVMIntPredicate llvm_cond)
|
{
|
LLVMBuilderRef builder = state->gallivm->builder;
|
LLVMValueRef next;
|
LLVMValueRef cond;
|
LLVMBasicBlockRef after_block;
|
|
if (!step)
|
step = LLVMConstInt(LLVMTypeOf(end), 1, 0);
|
|
next = LLVMBuildAdd(builder, state->counter, step, "");
|
|
LLVMBuildStore(builder, next, state->counter_var);
|
|
cond = LLVMBuildICmp(builder, llvm_cond, next, end, "");
|
|
after_block = lp_build_insert_new_block(state->gallivm, "loop_end");
|
|
LLVMBuildCondBr(builder, cond, after_block, state->block);
|
|
LLVMPositionBuilderAtEnd(builder, after_block);
|
|
state->counter = LLVMBuildLoad(builder, state->counter_var, "");
|
}
|
|
|
void
|
lp_build_loop_end(struct lp_build_loop_state *state,
|
LLVMValueRef end,
|
LLVMValueRef step)
|
{
|
lp_build_loop_end_cond(state, end, step, LLVMIntNE);
|
}
|
|
/**
|
* Creates a c-style for loop,
|
* contrasts lp_build_loop as this checks condition on entry
|
* e.g. for(i = start; i cmp_op end; i += step)
|
* \param state the for loop state, initialized here
|
* \param gallivm the gallivm state
|
* \param start starting value of iterator
|
* \param cmp_op comparison operator used for comparing current value with end value
|
* \param end value used to compare against iterator
|
* \param step value added to iterator at end of each loop
|
*/
|
void
|
lp_build_for_loop_begin(struct lp_build_for_loop_state *state,
|
struct gallivm_state *gallivm,
|
LLVMValueRef start,
|
LLVMIntPredicate cmp_op,
|
LLVMValueRef end,
|
LLVMValueRef step)
|
{
|
LLVMBuilderRef builder = gallivm->builder;
|
|
assert(LLVMTypeOf(start) == LLVMTypeOf(end));
|
assert(LLVMTypeOf(start) == LLVMTypeOf(step));
|
|
state->begin = lp_build_insert_new_block(gallivm, "loop_begin");
|
state->step = step;
|
state->counter_var = lp_build_alloca(gallivm, LLVMTypeOf(start), "loop_counter");
|
state->gallivm = gallivm;
|
state->cond = cmp_op;
|
state->end = end;
|
|
LLVMBuildStore(builder, start, state->counter_var);
|
LLVMBuildBr(builder, state->begin);
|
|
LLVMPositionBuilderAtEnd(builder, state->begin);
|
state->counter = LLVMBuildLoad(builder, state->counter_var, "");
|
|
state->body = lp_build_insert_new_block(gallivm, "loop_body");
|
LLVMPositionBuilderAtEnd(builder, state->body);
|
}
|
|
/**
|
* End the for loop.
|
*/
|
void
|
lp_build_for_loop_end(struct lp_build_for_loop_state *state)
|
{
|
LLVMValueRef next, cond;
|
LLVMBuilderRef builder = state->gallivm->builder;
|
|
next = LLVMBuildAdd(builder, state->counter, state->step, "");
|
LLVMBuildStore(builder, next, state->counter_var);
|
LLVMBuildBr(builder, state->begin);
|
|
state->exit = lp_build_insert_new_block(state->gallivm, "loop_exit");
|
|
/*
|
* We build the comparison for the begin block here,
|
* if we build it earlier the output llvm ir is not human readable
|
* as the code produced is not in the standard begin -> body -> end order.
|
*/
|
LLVMPositionBuilderAtEnd(builder, state->begin);
|
cond = LLVMBuildICmp(builder, state->cond, state->counter, state->end, "");
|
LLVMBuildCondBr(builder, cond, state->body, state->exit);
|
|
LLVMPositionBuilderAtEnd(builder, state->exit);
|
}
|
|
|
/*
|
Example of if/then/else building:
|
|
int x;
|
if (cond) {
|
x = 1 + 2;
|
}
|
else {
|
x = 2 + 3;
|
}
|
|
Is built with:
|
|
// x needs an alloca variable
|
x = lp_build_alloca(builder, type, "x");
|
|
|
lp_build_if(ctx, builder, cond);
|
LLVMBuildStore(LLVMBuildAdd(1, 2), x);
|
lp_build_else(ctx);
|
LLVMBuildStore(LLVMBuildAdd(2, 3). x);
|
lp_build_endif(ctx);
|
|
*/
|
|
|
|
/**
|
* Begin an if/else/endif construct.
|
*/
|
void
|
lp_build_if(struct lp_build_if_state *ifthen,
|
struct gallivm_state *gallivm,
|
LLVMValueRef condition)
|
{
|
LLVMBasicBlockRef block = LLVMGetInsertBlock(gallivm->builder);
|
|
memset(ifthen, 0, sizeof *ifthen);
|
ifthen->gallivm = gallivm;
|
ifthen->condition = condition;
|
ifthen->entry_block = block;
|
|
/* create endif/merge basic block for the phi functions */
|
ifthen->merge_block = lp_build_insert_new_block(gallivm, "endif-block");
|
|
/* create/insert true_block before merge_block */
|
ifthen->true_block =
|
LLVMInsertBasicBlockInContext(gallivm->context,
|
ifthen->merge_block,
|
"if-true-block");
|
|
/* successive code goes into the true block */
|
LLVMPositionBuilderAtEnd(gallivm->builder, ifthen->true_block);
|
}
|
|
|
/**
|
* Begin else-part of a conditional
|
*/
|
void
|
lp_build_else(struct lp_build_if_state *ifthen)
|
{
|
LLVMBuilderRef builder = ifthen->gallivm->builder;
|
|
/* Append an unconditional Br(anch) instruction on the true_block */
|
LLVMBuildBr(builder, ifthen->merge_block);
|
|
/* create/insert false_block before the merge block */
|
ifthen->false_block =
|
LLVMInsertBasicBlockInContext(ifthen->gallivm->context,
|
ifthen->merge_block,
|
"if-false-block");
|
|
/* successive code goes into the else block */
|
LLVMPositionBuilderAtEnd(builder, ifthen->false_block);
|
}
|
|
|
/**
|
* End a conditional.
|
*/
|
void
|
lp_build_endif(struct lp_build_if_state *ifthen)
|
{
|
LLVMBuilderRef builder = ifthen->gallivm->builder;
|
|
/* Insert branch to the merge block from current block */
|
LLVMBuildBr(builder, ifthen->merge_block);
|
|
/*
|
* Now patch in the various branch instructions.
|
*/
|
|
/* Insert the conditional branch instruction at the end of entry_block */
|
LLVMPositionBuilderAtEnd(builder, ifthen->entry_block);
|
if (ifthen->false_block) {
|
/* we have an else clause */
|
LLVMBuildCondBr(builder, ifthen->condition,
|
ifthen->true_block, ifthen->false_block);
|
}
|
else {
|
/* no else clause */
|
LLVMBuildCondBr(builder, ifthen->condition,
|
ifthen->true_block, ifthen->merge_block);
|
}
|
|
/* Resume building code at end of the ifthen->merge_block */
|
LLVMPositionBuilderAtEnd(builder, ifthen->merge_block);
|
}
|
|
|
static LLVMBuilderRef
|
create_builder_at_entry(struct gallivm_state *gallivm)
|
{
|
LLVMBuilderRef builder = gallivm->builder;
|
LLVMBasicBlockRef current_block = LLVMGetInsertBlock(builder);
|
LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
|
LLVMBasicBlockRef first_block = LLVMGetEntryBasicBlock(function);
|
LLVMValueRef first_instr = LLVMGetFirstInstruction(first_block);
|
LLVMBuilderRef first_builder = LLVMCreateBuilderInContext(gallivm->context);
|
|
if (first_instr) {
|
LLVMPositionBuilderBefore(first_builder, first_instr);
|
} else {
|
LLVMPositionBuilderAtEnd(first_builder, first_block);
|
}
|
|
return first_builder;
|
}
|
|
|
/**
|
* 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(struct gallivm_state *gallivm,
|
LLVMTypeRef type,
|
const char *name)
|
{
|
LLVMBuilderRef builder = gallivm->builder;
|
LLVMBuilderRef first_builder = create_builder_at_entry(gallivm);
|
LLVMValueRef res;
|
|
res = LLVMBuildAlloca(first_builder, type, name);
|
LLVMBuildStore(builder, LLVMConstNull(type), res);
|
|
LLVMDisposeBuilder(first_builder);
|
|
return res;
|
}
|
|
|
/**
|
* Like lp_build_alloca, but do not zero-initialize the variable.
|
*/
|
LLVMValueRef
|
lp_build_alloca_undef(struct gallivm_state *gallivm,
|
LLVMTypeRef type,
|
const char *name)
|
{
|
LLVMBuilderRef first_builder = create_builder_at_entry(gallivm);
|
LLVMValueRef res;
|
|
res = LLVMBuildAlloca(first_builder, type, name);
|
|
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(struct gallivm_state *gallivm,
|
LLVMTypeRef type,
|
LLVMValueRef count,
|
const char *name)
|
{
|
LLVMBuilderRef first_builder = create_builder_at_entry(gallivm);
|
LLVMValueRef res;
|
|
res = LLVMBuildArrayAlloca(first_builder, type, count, name);
|
|
LLVMDisposeBuilder(first_builder);
|
|
return res;
|
}
|
