src/gallium/auxiliary/gallivm/lp_bld_flow.c

   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@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    /* cond = (mask == 0) */
 135    cond = LLVMBuildICmp(builder,
 136                         LLVMIntEQ,
 137                         LLVMBuildBitCast(builder, value, mask->reg_type, ""),
 138                         LLVMConstNull(mask->reg_type),
 139                         "");
 140
 141    /* if cond, goto end of block */
 142    lp_build_flow_skip_cond_break(&mask->skip, cond);
 143 }
 144
 145
 146 /**
 147  * Begin a section of code which is predicated on a mask.
 148  * \param mask  the mask context, initialized here
 149  * \param flow  the flow context
 150  * \param type  the type of the mask
 151  * \param value  storage for the mask
 152  */
 153 void
 154 lp_build_mask_begin(struct lp_build_mask_context *mask,
 155                     struct gallivm_state *gallivm,
 156                     struct lp_type type,
 157                     LLVMValueRef value)
 158 {
 159    memset(mask, 0, sizeof *mask);
 160
 161    mask->reg_type = LLVMIntTypeInContext(gallivm->context, type.width * type.length);
 162    mask->var = lp_build_alloca(gallivm,
 163                                lp_build_int_vec_type(gallivm, type),
 164                                "execution_mask");
 165
 166    LLVMBuildStore(gallivm->builder, value, mask->var);
 167
 168    lp_build_flow_skip_begin(&mask->skip, gallivm);
 169 }
 170
 171
 172 LLVMValueRef
 173 lp_build_mask_value(struct lp_build_mask_context *mask)
 174 {
 175    return LLVMBuildLoad(mask->skip.gallivm->builder, mask->var, "");
 176 }
 177
 178
 179 /**
 180  * Update boolean mask with given value (bitwise AND).
 181  * Typically used to update the quad's pixel alive/killed mask
 182  * after depth testing, alpha testing, TGSI_OPCODE_KIL, etc.
 183  */
 184 void
 185 lp_build_mask_update(struct lp_build_mask_context *mask,
 186                      LLVMValueRef value)
 187 {
 188    value = LLVMBuildAnd(mask->skip.gallivm->builder,
 189                         lp_build_mask_value(mask),
 190                         value, "");
 191    LLVMBuildStore(mask->skip.gallivm->builder, value, mask->var);
 192 }
 193
 194
 195 /**
 196  * End section of code which is predicated on a mask.
 197  */
 198 LLVMValueRef
 199 lp_build_mask_end(struct lp_build_mask_context *mask)
 200 {
 201    lp_build_flow_skip_end(&mask->skip);
 202    return lp_build_mask_value(mask);
 203 }
 204
 205
 206
 207 void
 208 lp_build_loop_begin(struct lp_build_loop_state *state,
 209                     struct gallivm_state *gallivm,
 210                     LLVMValueRef start)
 211
 212 {
 213    LLVMBuilderRef builder = gallivm->builder;
 214
 215    state->block = lp_build_insert_new_block(gallivm, "loop_begin");
 216
 217    state->counter_var = lp_build_alloca(gallivm, LLVMTypeOf(start), "loop_counter");
 218    state->gallivm = gallivm;
 219
 220    LLVMBuildStore(builder, start, state->counter_var);
 221
 222    LLVMBuildBr(builder, state->block);
 223
 224    LLVMPositionBuilderAtEnd(builder, state->block);
 225
 226    state->counter = LLVMBuildLoad(builder, state->counter_var, "");
 227 }
 228
 229
 230 void
 231 lp_build_loop_end_cond(struct lp_build_loop_state *state,
 232                        LLVMValueRef end,
 233                        LLVMValueRef step,
 234                        LLVMIntPredicate llvm_cond)
 235 {
 236    LLVMBuilderRef builder = state->gallivm->builder;
 237    LLVMValueRef next;
 238    LLVMValueRef cond;
 239    LLVMBasicBlockRef after_block;
 240
 241    if (!step)
 242       step = LLVMConstInt(LLVMTypeOf(end), 1, 0);
 243
 244    next = LLVMBuildAdd(builder, state->counter, step, "");
 245
 246    LLVMBuildStore(builder, next, state->counter_var);
 247
 248    cond = LLVMBuildICmp(builder, llvm_cond, next, end, "");
 249
 250    after_block = lp_build_insert_new_block(state->gallivm, "loop_end");
 251
 252    LLVMBuildCondBr(builder, cond, after_block, state->block);
 253
 254    LLVMPositionBuilderAtEnd(builder, after_block);
 255
 256    state->counter = LLVMBuildLoad(builder, state->counter_var, "");
 257 }
 258
 259
 260 void
 261 lp_build_loop_end(struct lp_build_loop_state *state,
 262                   LLVMValueRef end,
 263                   LLVMValueRef step)
 264 {
 265    lp_build_loop_end_cond(state, end, step, LLVMIntNE);
 266 }
 267
 268
 269
 270 /*
 271   Example of if/then/else building:
 272
 273      int x;
 274      if (cond) {
 275         x = 1 + 2;
 276      }
 277      else {
 278         x = 2 + 3;
 279      }
 280
 281   Is built with:
 282
 283      // x needs an alloca variable
 284      x = lp_build_alloca(builder, type, "x");
 285
 286
 287      lp_build_if(ctx, builder, cond);
 288         LLVMBuildStore(LLVMBuildAdd(1, 2), x);
 289      lp_build_else(ctx);
 290         LLVMBuildStore(LLVMBuildAdd(2, 3). x);
 291      lp_build_endif(ctx);
 292
 293  */
 294
 295
 296
 297 /**
 298  * Begin an if/else/endif construct.
 299  */
 300 void
 301 lp_build_if(struct lp_build_if_state *ifthen,
 302             struct gallivm_state *gallivm,
 303             LLVMValueRef condition)
 304 {
 305    LLVMBasicBlockRef block = LLVMGetInsertBlock(gallivm->builder);
 306
 307    memset(ifthen, 0, sizeof *ifthen);
 308    ifthen->gallivm = gallivm;
 309    ifthen->condition = condition;
 310    ifthen->entry_block = block;
 311
 312    /* create endif/merge basic block for the phi functions */
 313    ifthen->merge_block = lp_build_insert_new_block(gallivm, "endif-block");
 314
 315    /* create/insert true_block before merge_block */
 316    ifthen->true_block =
 317       LLVMInsertBasicBlockInContext(gallivm->context,
 318                                     ifthen->merge_block,
 319                                     "if-true-block");
 320
 321    /* successive code goes into the true block */
 322    LLVMPositionBuilderAtEnd(gallivm->builder, ifthen->true_block);
 323 }
 324
 325
 326 /**
 327  * Begin else-part of a conditional
 328  */
 329 void
 330 lp_build_else(struct lp_build_if_state *ifthen)
 331 {
 332    LLVMBuilderRef builder = ifthen->gallivm->builder;
 333
 334    /* Append an unconditional Br(anch) instruction on the true_block */
 335    LLVMBuildBr(builder, ifthen->merge_block);
 336
 337    /* create/insert false_block before the merge block */
 338    ifthen->false_block =
 339       LLVMInsertBasicBlockInContext(ifthen->gallivm->context,
 340                                     ifthen->merge_block,
 341                                     "if-false-block");
 342
 343    /* successive code goes into the else block */
 344    LLVMPositionBuilderAtEnd(builder, ifthen->false_block);
 345 }
 346
 347
 348 /**
 349  * End a conditional.
 350  */
 351 void
 352 lp_build_endif(struct lp_build_if_state *ifthen)
 353 {
 354    LLVMBuilderRef builder = ifthen->gallivm->builder;
 355
 356    /* Insert branch to the merge block from current block */
 357    LLVMBuildBr(builder, ifthen->merge_block);
 358
 359    /*
 360     * Now patch in the various branch instructions.
 361     */
 362
 363    /* Insert the conditional branch instruction at the end of entry_block */
 364    LLVMPositionBuilderAtEnd(builder, ifthen->entry_block);
 365    if (ifthen->false_block) {
 366       /* we have an else clause */
 367       LLVMBuildCondBr(builder, ifthen->condition,
 368                       ifthen->true_block, ifthen->false_block);
 369    }
 370    else {
 371       /* no else clause */
 372       LLVMBuildCondBr(builder, ifthen->condition,
 373                       ifthen->true_block, ifthen->merge_block);
 374    }
 375
 376    /* Resume building code at end of the ifthen->merge_block */
 377    LLVMPositionBuilderAtEnd(builder, ifthen->merge_block);
 378 }
 379
 380
 381 /**
 382  * Allocate a scalar (or vector) variable.
 383  *
 384  * Although not strictly part of control flow, control flow has deep impact in
 385  * how variables should be allocated.
 386  *
 387  * The mem2reg optimization pass is the recommended way to dealing with mutable
 388  * variables, and SSA. It looks for allocas and if it can handle them, it
 389  * promotes them, but only looks for alloca instructions in the entry block of
 390  * the function. Being in the entry block guarantees that the alloca is only
 391  * executed once, which makes analysis simpler.
 392  *
 393  * See also:
 394  * - http://www.llvm.org/docs/tutorial/OCamlLangImpl7.html#memory
 395  */
 396 LLVMValueRef
 397 lp_build_alloca(struct gallivm_state *gallivm,
 398                 LLVMTypeRef type,
 399                 const char *name)
 400 {
 401    LLVMBuilderRef builder = gallivm->builder;
 402    LLVMBasicBlockRef current_block = LLVMGetInsertBlock(builder);
 403    LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
 404    LLVMBasicBlockRef first_block = LLVMGetEntryBasicBlock(function);
 405    LLVMValueRef first_instr = LLVMGetFirstInstruction(first_block);
 406    LLVMBuilderRef first_builder = LLVMCreateBuilderInContext(gallivm->context);
 407    LLVMValueRef res;
 408
 409    if (first_instr) {
 410       LLVMPositionBuilderBefore(first_builder, first_instr);
 411    } else {
 412       LLVMPositionBuilderAtEnd(first_builder, first_block);
 413    }
 414
 415    res = LLVMBuildAlloca(first_builder, type, name);
 416    LLVMBuildStore(builder, LLVMConstNull(type), res);
 417
 418    LLVMDisposeBuilder(first_builder);
 419
 420    return res;
 421 }
 422
 423
 424 /**
 425  * Allocate an array of scalars/vectors.
 426  *
 427  * mem2reg pass is not capable of promoting structs or arrays to registers, but
 428  * we still put it in the first block anyway as failure to put allocas in the
 429  * first block may prevent the X86 backend from successfully align the stack as
 430  * required.
 431  *
 432  * Also the scalarrepl pass is supposedly more powerful and can promote
 433  * arrays in many cases.
 434  *
 435  * See also:
 436  * - http://www.llvm.org/docs/tutorial/OCamlLangImpl7.html#memory
 437  */
 438 LLVMValueRef
 439 lp_build_array_alloca(struct gallivm_state *gallivm,
 440                       LLVMTypeRef type,
 441                       LLVMValueRef count,
 442                       const char *name)
 443 {
 444    LLVMBuilderRef builder = gallivm->builder;
 445    LLVMBasicBlockRef current_block = LLVMGetInsertBlock(builder);
 446    LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
 447    LLVMBasicBlockRef first_block = LLVMGetEntryBasicBlock(function);
 448    LLVMValueRef first_instr = LLVMGetFirstInstruction(first_block);
 449    LLVMBuilderRef first_builder = LLVMCreateBuilderInContext(gallivm->context);
 450    LLVMValueRef res;
 451
 452    if (first_instr) {
 453       LLVMPositionBuilderBefore(first_builder, first_instr);
 454    } else {
 455       LLVMPositionBuilderAtEnd(first_builder, first_block);
 456    }
 457
 458    res = LLVMBuildArrayAlloca(first_builder, type, count, name);
 459
 460    LLVMDisposeBuilder(first_builder);
 461
 462    return res;
 463 }