Home | History | Annotate | Download | only in gallivm
      1 /**************************************************************************
      2  *
      3  * Copyright 2009 VMware, Inc.
      4  * All Rights Reserved.
      5  *
      6  * Permission is hereby granted, free of charge, to any person obtaining a
      7  * copy of this software and associated documentation files (the
      8  * "Software"), to deal in the Software without restriction, including
      9  * without limitation the rights to use, copy, modify, merge, publish,
     10  * distribute, sub license, and/or sell copies of the Software, and to
     11  * permit persons to whom the Software is furnished to do so, subject to
     12  * the following conditions:
     13  *
     14  * The above copyright notice and this permission notice (including the
     15  * next paragraph) shall be included in all copies or substantial portions
     16  * of the Software.
     17  *
     18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
     19  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
     20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
     21  * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
     22  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
     23  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
     24  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
     25  *
     26  **************************************************************************/
     27 
     28 /**
     29  * LLVM control flow build helpers.
     30  *
     31  * @author Jose Fonseca <jfonseca (at) vmware.com>
     32  */
     33 
     34 #include "util/u_debug.h"
     35 #include "util/u_memory.h"
     36 
     37 #include "lp_bld_init.h"
     38 #include "lp_bld_type.h"
     39 #include "lp_bld_flow.h"
     40 
     41 
     42 /**
     43  * Insert a new block, right where builder is pointing to.
     44  *
     45  * This is useful important not only for aesthetic reasons, but also for
     46  * performance reasons, as frequently run blocks should be laid out next to
     47  * each other and fall-throughs maximized.
     48  *
     49  * See also llvm/lib/Transforms/Scalar/BasicBlockPlacement.cpp.
     50  *
     51  * Note: this function has no dependencies on the flow code and could
     52  * be used elsewhere.
     53  */
     54 LLVMBasicBlockRef
     55 lp_build_insert_new_block(struct gallivm_state *gallivm, const char *name)
     56 {
     57    LLVMBasicBlockRef current_block;
     58    LLVMBasicBlockRef next_block;
     59    LLVMBasicBlockRef new_block;
     60 
     61    /* get current basic block */
     62    current_block = LLVMGetInsertBlock(gallivm->builder);
     63 
     64    /* check if there's another block after this one */
     65    next_block = LLVMGetNextBasicBlock(current_block);
     66    if (next_block) {
     67       /* insert the new block before the next block */
     68       new_block = LLVMInsertBasicBlockInContext(gallivm->context, next_block, name);
     69    }
     70    else {
     71       /* append new block after current block */
     72       LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
     73       new_block = LLVMAppendBasicBlockInContext(gallivm->context, function, name);
     74    }
     75 
     76    return new_block;
     77 }
     78 
     79 
     80 /**
     81  * Begin a "skip" block.  Inside this block we can test a condition and
     82  * skip to the end of the block if the condition is false.
     83  */
     84 void
     85 lp_build_flow_skip_begin(struct lp_build_skip_context *skip,
     86                          struct gallivm_state *gallivm)
     87 {
     88    skip->gallivm = gallivm;
     89    /* create new basic block */
     90    skip->block = lp_build_insert_new_block(gallivm, "skip");
     91 }
     92 
     93 
     94 /**
     95  * Insert code to test a condition and branch to the end of the current
     96  * skip block if the condition is true.
     97  */
     98 void
     99 lp_build_flow_skip_cond_break(struct lp_build_skip_context *skip,
    100                               LLVMValueRef cond)
    101 {
    102    LLVMBasicBlockRef new_block;
    103 
    104    new_block = lp_build_insert_new_block(skip->gallivm, "");
    105 
    106    /* if cond is true, goto skip->block, else goto new_block */
    107    LLVMBuildCondBr(skip->gallivm->builder, cond, skip->block, new_block);
    108 
    109    LLVMPositionBuilderAtEnd(skip->gallivm->builder, new_block);
    110 }
    111 
    112 
    113 void
    114 lp_build_flow_skip_end(struct lp_build_skip_context *skip)
    115 {
    116    /* goto block */
    117    LLVMBuildBr(skip->gallivm->builder, skip->block);
    118    LLVMPositionBuilderAtEnd(skip->gallivm->builder, skip->block);
    119 }
    120 
    121 
    122 /**
    123  * Check if the mask predicate is zero.  If so, jump to the end of the block.
    124  */
    125 void
    126 lp_build_mask_check(struct lp_build_mask_context *mask)
    127 {
    128    LLVMBuilderRef builder = mask->skip.gallivm->builder;
    129    LLVMValueRef value;
    130    LLVMValueRef cond;
    131 
    132    value = lp_build_mask_value(mask);
    133 
    134    /*
    135     * XXX this doesn't quite generate the most efficient code possible, if
    136     * the masks are vectors which have all bits set to the same value
    137     * in each element.
    138     * movmskps/pmovmskb would be more efficient to get the required value
    139     * into ordinary reg (certainly with 8 floats).
    140     * Not sure if llvm could figure that out on its own.
    141     */
    142 
    143    /* cond = (mask == 0) */
    144    cond = LLVMBuildICmp(builder,
    145                         LLVMIntEQ,
    146                         LLVMBuildBitCast(builder, value, mask->reg_type, ""),
    147                         LLVMConstNull(mask->reg_type),
    148                         "");
    149 
    150    /* if cond, goto end of block */
    151    lp_build_flow_skip_cond_break(&mask->skip, cond);
    152 }
    153 
    154 
    155 /**
    156  * Begin a section of code which is predicated on a mask.
    157  * \param mask  the mask context, initialized here
    158  * \param flow  the flow context
    159  * \param type  the type of the mask
    160  * \param value  storage for the mask
    161  */
    162 void
    163 lp_build_mask_begin(struct lp_build_mask_context *mask,
    164                     struct gallivm_state *gallivm,
    165                     struct lp_type type,
    166                     LLVMValueRef value)
    167 {
    168    memset(mask, 0, sizeof *mask);
    169 
    170    mask->reg_type = LLVMIntTypeInContext(gallivm->context, type.width * type.length);
    171    mask->var = lp_build_alloca(gallivm,
    172                                lp_build_int_vec_type(gallivm, type),
    173                                "execution_mask");
    174 
    175    LLVMBuildStore(gallivm->builder, value, mask->var);
    176 
    177    lp_build_flow_skip_begin(&mask->skip, gallivm);
    178 }
    179 
    180 
    181 LLVMValueRef
    182 lp_build_mask_value(struct lp_build_mask_context *mask)
    183 {
    184    return LLVMBuildLoad(mask->skip.gallivm->builder, mask->var, "");
    185 }
    186 
    187 
    188 /**
    189  * Update boolean mask with given value (bitwise AND).
    190  * Typically used to update the quad's pixel alive/killed mask
    191  * after depth testing, alpha testing, TGSI_OPCODE_KIL, etc.
    192  */
    193 void
    194 lp_build_mask_update(struct lp_build_mask_context *mask,
    195                      LLVMValueRef value)
    196 {
    197    value = LLVMBuildAnd(mask->skip.gallivm->builder,
    198                         lp_build_mask_value(mask),
    199                         value, "");
    200    LLVMBuildStore(mask->skip.gallivm->builder, value, mask->var);
    201 }
    202 
    203 
    204 /**
    205  * End section of code which is predicated on a mask.
    206  */
    207 LLVMValueRef
    208 lp_build_mask_end(struct lp_build_mask_context *mask)
    209 {
    210    lp_build_flow_skip_end(&mask->skip);
    211    return lp_build_mask_value(mask);
    212 }
    213 
    214 
    215 
    216 void
    217 lp_build_loop_begin(struct lp_build_loop_state *state,
    218                     struct gallivm_state *gallivm,
    219                     LLVMValueRef start)
    220 
    221 {
    222    LLVMBuilderRef builder = gallivm->builder;
    223 
    224    state->block = lp_build_insert_new_block(gallivm, "loop_begin");
    225 
    226    state->counter_var = lp_build_alloca(gallivm, LLVMTypeOf(start), "loop_counter");
    227    state->gallivm = gallivm;
    228 
    229    LLVMBuildStore(builder, start, state->counter_var);
    230 
    231    LLVMBuildBr(builder, state->block);
    232 
    233    LLVMPositionBuilderAtEnd(builder, state->block);
    234 
    235    state->counter = LLVMBuildLoad(builder, state->counter_var, "");
    236 }
    237 
    238 
    239 void
    240 lp_build_loop_end_cond(struct lp_build_loop_state *state,
    241                        LLVMValueRef end,
    242                        LLVMValueRef step,
    243                        LLVMIntPredicate llvm_cond)
    244 {
    245    LLVMBuilderRef builder = state->gallivm->builder;
    246    LLVMValueRef next;
    247    LLVMValueRef cond;
    248    LLVMBasicBlockRef after_block;
    249 
    250    if (!step)
    251       step = LLVMConstInt(LLVMTypeOf(end), 1, 0);
    252 
    253    next = LLVMBuildAdd(builder, state->counter, step, "");
    254 
    255    LLVMBuildStore(builder, next, state->counter_var);
    256 
    257    cond = LLVMBuildICmp(builder, llvm_cond, next, end, "");
    258 
    259    after_block = lp_build_insert_new_block(state->gallivm, "loop_end");
    260 
    261    LLVMBuildCondBr(builder, cond, after_block, state->block);
    262 
    263    LLVMPositionBuilderAtEnd(builder, after_block);
    264 
    265    state->counter = LLVMBuildLoad(builder, state->counter_var, "");
    266 }
    267 
    268 
    269 void
    270 lp_build_loop_end(struct lp_build_loop_state *state,
    271                   LLVMValueRef end,
    272                   LLVMValueRef step)
    273 {
    274    lp_build_loop_end_cond(state, end, step, LLVMIntNE);
    275 }
    276 
    277 /**
    278  * Creates a c-style for loop,
    279  * contrasts lp_build_loop as this checks condition on entry
    280  * e.g. for(i = start; i cmp_op end; i += step)
    281  * \param state      the for loop state, initialized here
    282  * \param gallivm    the gallivm state
    283  * \param start      starting value of iterator
    284  * \param cmp_op     comparison operator used for comparing current value with end value
    285  * \param end        value used to compare against iterator
    286  * \param step       value added to iterator at end of each loop
    287  */
    288 void
    289 lp_build_for_loop_begin(struct lp_build_for_loop_state *state,
    290                         struct gallivm_state *gallivm,
    291                         LLVMValueRef start,
    292                         LLVMIntPredicate cmp_op,
    293                         LLVMValueRef end,
    294                         LLVMValueRef step)
    295 {
    296    LLVMBuilderRef builder = gallivm->builder;
    297 
    298    assert(LLVMTypeOf(start) == LLVMTypeOf(end));
    299    assert(LLVMTypeOf(start) == LLVMTypeOf(step));
    300 
    301    state->begin = lp_build_insert_new_block(gallivm, "loop_begin");
    302    state->step  = step;
    303    state->counter_var = lp_build_alloca(gallivm, LLVMTypeOf(start), "loop_counter");
    304    state->gallivm = gallivm;
    305    state->cond = cmp_op;
    306    state->end = end;
    307 
    308    LLVMBuildStore(builder, start, state->counter_var);
    309    LLVMBuildBr(builder, state->begin);
    310 
    311    LLVMPositionBuilderAtEnd(builder, state->begin);
    312    state->counter = LLVMBuildLoad(builder, state->counter_var, "");
    313 
    314    state->body = lp_build_insert_new_block(gallivm, "loop_body");
    315    LLVMPositionBuilderAtEnd(builder, state->body);
    316 }
    317 
    318 /**
    319  * End the for loop.
    320  */
    321 void
    322 lp_build_for_loop_end(struct lp_build_for_loop_state *state)
    323 {
    324    LLVMValueRef next, cond;
    325    LLVMBuilderRef builder = state->gallivm->builder;
    326 
    327    next = LLVMBuildAdd(builder, state->counter, state->step, "");
    328    LLVMBuildStore(builder, next, state->counter_var);
    329    LLVMBuildBr(builder, state->begin);
    330 
    331    state->exit = lp_build_insert_new_block(state->gallivm, "loop_exit");
    332 
    333    /*
    334     * We build the comparison for the begin block here,
    335     * if we build it earlier the output llvm ir is not human readable
    336     * as the code produced is not in the standard begin -> body -> end order.
    337     */
    338    LLVMPositionBuilderAtEnd(builder, state->begin);
    339    cond = LLVMBuildICmp(builder, state->cond, state->counter, state->end, "");
    340    LLVMBuildCondBr(builder, cond, state->body, state->exit);
    341 
    342    LLVMPositionBuilderAtEnd(builder, state->exit);
    343 }
    344 
    345 
    346 /*
    347   Example of if/then/else building:
    348 
    349      int x;
    350      if (cond) {
    351         x = 1 + 2;
    352      }
    353      else {
    354         x = 2 + 3;
    355      }
    356 
    357   Is built with:
    358 
    359      // x needs an alloca variable
    360      x = lp_build_alloca(builder, type, "x");
    361 
    362 
    363      lp_build_if(ctx, builder, cond);
    364         LLVMBuildStore(LLVMBuildAdd(1, 2), x);
    365      lp_build_else(ctx);
    366         LLVMBuildStore(LLVMBuildAdd(2, 3). x);
    367      lp_build_endif(ctx);
    368 
    369  */
    370 
    371 
    372 
    373 /**
    374  * Begin an if/else/endif construct.
    375  */
    376 void
    377 lp_build_if(struct lp_build_if_state *ifthen,
    378             struct gallivm_state *gallivm,
    379             LLVMValueRef condition)
    380 {
    381    LLVMBasicBlockRef block = LLVMGetInsertBlock(gallivm->builder);
    382 
    383    memset(ifthen, 0, sizeof *ifthen);
    384    ifthen->gallivm = gallivm;
    385    ifthen->condition = condition;
    386    ifthen->entry_block = block;
    387 
    388    /* create endif/merge basic block for the phi functions */
    389    ifthen->merge_block = lp_build_insert_new_block(gallivm, "endif-block");
    390 
    391    /* create/insert true_block before merge_block */
    392    ifthen->true_block =
    393       LLVMInsertBasicBlockInContext(gallivm->context,
    394                                     ifthen->merge_block,
    395                                     "if-true-block");
    396 
    397    /* successive code goes into the true block */
    398    LLVMPositionBuilderAtEnd(gallivm->builder, ifthen->true_block);
    399 }
    400 
    401 
    402 /**
    403  * Begin else-part of a conditional
    404  */
    405 void
    406 lp_build_else(struct lp_build_if_state *ifthen)
    407 {
    408    LLVMBuilderRef builder = ifthen->gallivm->builder;
    409 
    410    /* Append an unconditional Br(anch) instruction on the true_block */
    411    LLVMBuildBr(builder, ifthen->merge_block);
    412 
    413    /* create/insert false_block before the merge block */
    414    ifthen->false_block =
    415       LLVMInsertBasicBlockInContext(ifthen->gallivm->context,
    416                                     ifthen->merge_block,
    417                                     "if-false-block");
    418 
    419    /* successive code goes into the else block */
    420    LLVMPositionBuilderAtEnd(builder, ifthen->false_block);
    421 }
    422 
    423 
    424 /**
    425  * End a conditional.
    426  */
    427 void
    428 lp_build_endif(struct lp_build_if_state *ifthen)
    429 {
    430    LLVMBuilderRef builder = ifthen->gallivm->builder;
    431 
    432    /* Insert branch to the merge block from current block */
    433    LLVMBuildBr(builder, ifthen->merge_block);
    434 
    435    /*
    436     * Now patch in the various branch instructions.
    437     */
    438 
    439    /* Insert the conditional branch instruction at the end of entry_block */
    440    LLVMPositionBuilderAtEnd(builder, ifthen->entry_block);
    441    if (ifthen->false_block) {
    442       /* we have an else clause */
    443       LLVMBuildCondBr(builder, ifthen->condition,
    444                       ifthen->true_block, ifthen->false_block);
    445    }
    446    else {
    447       /* no else clause */
    448       LLVMBuildCondBr(builder, ifthen->condition,
    449                       ifthen->true_block, ifthen->merge_block);
    450    }
    451 
    452    /* Resume building code at end of the ifthen->merge_block */
    453    LLVMPositionBuilderAtEnd(builder, ifthen->merge_block);
    454 }
    455 
    456 
    457 /**
    458  * Allocate a scalar (or vector) variable.
    459  *
    460  * Although not strictly part of control flow, control flow has deep impact in
    461  * how variables should be allocated.
    462  *
    463  * The mem2reg optimization pass is the recommended way to dealing with mutable
    464  * variables, and SSA. It looks for allocas and if it can handle them, it
    465  * promotes them, but only looks for alloca instructions in the entry block of
    466  * the function. Being in the entry block guarantees that the alloca is only
    467  * executed once, which makes analysis simpler.
    468  *
    469  * See also:
    470  * - http://www.llvm.org/docs/tutorial/OCamlLangImpl7.html#memory
    471  */
    472 LLVMValueRef
    473 lp_build_alloca(struct gallivm_state *gallivm,
    474                 LLVMTypeRef type,
    475                 const char *name)
    476 {
    477    LLVMBuilderRef builder = gallivm->builder;
    478    LLVMBasicBlockRef current_block = LLVMGetInsertBlock(builder);
    479    LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
    480    LLVMBasicBlockRef first_block = LLVMGetEntryBasicBlock(function);
    481    LLVMValueRef first_instr = LLVMGetFirstInstruction(first_block);
    482    LLVMBuilderRef first_builder = LLVMCreateBuilderInContext(gallivm->context);
    483    LLVMValueRef res;
    484 
    485    if (first_instr) {
    486       LLVMPositionBuilderBefore(first_builder, first_instr);
    487    } else {
    488       LLVMPositionBuilderAtEnd(first_builder, first_block);
    489    }
    490 
    491    res = LLVMBuildAlloca(first_builder, type, name);
    492    LLVMBuildStore(builder, LLVMConstNull(type), res);
    493 
    494    LLVMDisposeBuilder(first_builder);
    495 
    496    return res;
    497 }
    498 
    499 
    500 /**
    501  * Allocate an array of scalars/vectors.
    502  *
    503  * mem2reg pass is not capable of promoting structs or arrays to registers, but
    504  * we still put it in the first block anyway as failure to put allocas in the
    505  * first block may prevent the X86 backend from successfully align the stack as
    506  * required.
    507  *
    508  * Also the scalarrepl pass is supposedly more powerful and can promote
    509  * arrays in many cases.
    510  *
    511  * See also:
    512  * - http://www.llvm.org/docs/tutorial/OCamlLangImpl7.html#memory
    513  */
    514 LLVMValueRef
    515 lp_build_array_alloca(struct gallivm_state *gallivm,
    516                       LLVMTypeRef type,
    517                       LLVMValueRef count,
    518                       const char *name)
    519 {
    520    LLVMBuilderRef builder = gallivm->builder;
    521    LLVMBasicBlockRef current_block = LLVMGetInsertBlock(builder);
    522    LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
    523    LLVMBasicBlockRef first_block = LLVMGetEntryBasicBlock(function);
    524    LLVMValueRef first_instr = LLVMGetFirstInstruction(first_block);
    525    LLVMBuilderRef first_builder = LLVMCreateBuilderInContext(gallivm->context);
    526    LLVMValueRef res;
    527 
    528    if (first_instr) {
    529       LLVMPositionBuilderBefore(first_builder, first_instr);
    530    } else {
    531       LLVMPositionBuilderAtEnd(first_builder, first_block);
    532    }
    533 
    534    res = LLVMBuildArrayAlloca(first_builder, type, count, name);
    535 
    536    LLVMDisposeBuilder(first_builder);
    537 
    538    return res;
    539 }
    540