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    /*
 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_KILL_IF, 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  * Update boolean mask with given value.
 205  * Used for per-sample shading to force per-sample execution masks.
 206  */
 207 void
 208 lp_build_mask_force(struct lp_build_mask_context *mask,
 209                     LLVMValueRef value)
 210 {
 211    LLVMBuildStore(mask->skip.gallivm->builder, value, mask->var);
 212 }
 213
 214 /**
 215  * End section of code which is predicated on a mask.
 216  */
 217 LLVMValueRef
 218 lp_build_mask_end(struct lp_build_mask_context *mask)
 219 {
 220    lp_build_flow_skip_end(&mask->skip);
 221    return lp_build_mask_value(mask);
 222 }
 223
 224
 225
 226 void
 227 lp_build_loop_begin(struct lp_build_loop_state *state,
 228                     struct gallivm_state *gallivm,
 229                     LLVMValueRef start)
 230
 231 {
 232    LLVMBuilderRef builder = gallivm->builder;
 233
 234    state->block = lp_build_insert_new_block(gallivm, "loop_begin");
 235
 236    state->counter_var = lp_build_alloca(gallivm, LLVMTypeOf(start), "loop_counter");
 237    state->gallivm = gallivm;
 238
 239    LLVMBuildStore(builder, start, state->counter_var);
 240
 241    LLVMBuildBr(builder, state->block);
 242
 243    LLVMPositionBuilderAtEnd(builder, state->block);
 244
 245    state->counter = LLVMBuildLoad(builder, state->counter_var, "");
 246 }
 247
 248
 249 void
 250 lp_build_loop_end_cond(struct lp_build_loop_state *state,
 251                        LLVMValueRef end,
 252                        LLVMValueRef step,
 253                        LLVMIntPredicate llvm_cond)
 254 {
 255    LLVMBuilderRef builder = state->gallivm->builder;
 256    LLVMValueRef next;
 257    LLVMValueRef cond;
 258    LLVMBasicBlockRef after_block;
 259
 260    if (!step)
 261       step = LLVMConstInt(LLVMTypeOf(end), 1, 0);
 262
 263    next = LLVMBuildAdd(builder, state->counter, step, "");
 264
 265    LLVMBuildStore(builder, next, state->counter_var);
 266
 267    cond = LLVMBuildICmp(builder, llvm_cond, next, end, "");
 268
 269    after_block = lp_build_insert_new_block(state->gallivm, "loop_end");
 270
 271    LLVMBuildCondBr(builder, cond, after_block, state->block);
 272
 273    LLVMPositionBuilderAtEnd(builder, after_block);
 274
 275    state->counter = LLVMBuildLoad(builder, state->counter_var, "");
 276 }
 277
 278 void
 279 lp_build_loop_force_set_counter(struct lp_build_loop_state *state,
 280                           LLVMValueRef end)
 281 {
 282    LLVMBuilderRef builder = state->gallivm->builder;
 283    LLVMBuildStore(builder, end, state->counter_var);
 284 }
 285
 286 void
 287 lp_build_loop_force_reload_counter(struct lp_build_loop_state *state)
 288 {
 289    LLVMBuilderRef builder = state->gallivm->builder;
 290    state->counter = LLVMBuildLoad(builder, state->counter_var, "");
 291 }
 292
 293 void
 294 lp_build_loop_end(struct lp_build_loop_state *state,
 295                   LLVMValueRef end,
 296                   LLVMValueRef step)
 297 {
 298    lp_build_loop_end_cond(state, end, step, LLVMIntNE);
 299 }
 300
 301 /**
 302  * Creates a c-style for loop,
 303  * contrasts lp_build_loop as this checks condition on entry
 304  * e.g. for(i = start; i cmp_op end; i += step)
 305  * \param state      the for loop state, initialized here
 306  * \param gallivm    the gallivm state
 307  * \param start      starting value of iterator
 308  * \param cmp_op     comparison operator used for comparing current value with end value
 309  * \param end        value used to compare against iterator
 310  * \param step       value added to iterator at end of each loop
 311  */
 312 void
 313 lp_build_for_loop_begin(struct lp_build_for_loop_state *state,
 314                         struct gallivm_state *gallivm,
 315                         LLVMValueRef start,
 316                         LLVMIntPredicate cmp_op,
 317                         LLVMValueRef end,
 318                         LLVMValueRef step)
 319 {
 320    LLVMBuilderRef builder = gallivm->builder;
 321
 322    assert(LLVMTypeOf(start) == LLVMTypeOf(end));
 323    assert(LLVMTypeOf(start) == LLVMTypeOf(step));
 324
 325    state->begin = lp_build_insert_new_block(gallivm, "loop_begin");
 326    state->step  = step;
 327    state->counter_var = lp_build_alloca(gallivm, LLVMTypeOf(start), "loop_counter");
 328    state->gallivm = gallivm;
 329    state->cond = cmp_op;
 330    state->end = end;
 331
 332    LLVMBuildStore(builder, start, state->counter_var);
 333    LLVMBuildBr(builder, state->begin);
 334
 335    LLVMPositionBuilderAtEnd(builder, state->begin);
 336    state->counter = LLVMBuildLoad(builder, state->counter_var, "");
 337
 338    state->body = lp_build_insert_new_block(gallivm, "loop_body");
 339    LLVMPositionBuilderAtEnd(builder, state->body);
 340 }
 341
 342 /**
 343  * End the for loop.
 344  */
 345 void
 346 lp_build_for_loop_end(struct lp_build_for_loop_state *state)
 347 {
 348    LLVMValueRef next, cond;
 349    LLVMBuilderRef builder = state->gallivm->builder;
 350
 351    next = LLVMBuildAdd(builder, state->counter, state->step, "");
 352    LLVMBuildStore(builder, next, state->counter_var);
 353    LLVMBuildBr(builder, state->begin);
 354
 355    state->exit = lp_build_insert_new_block(state->gallivm, "loop_exit");
 356
 357    /*
 358     * We build the comparison for the begin block here,
 359     * if we build it earlier the output llvm ir is not human readable
 360     * as the code produced is not in the standard begin -> body -> end order.
 361     */
 362    LLVMPositionBuilderAtEnd(builder, state->begin);
 363    cond = LLVMBuildICmp(builder, state->cond, state->counter, state->end, "");
 364    LLVMBuildCondBr(builder, cond, state->body, state->exit);
 365
 366    LLVMPositionBuilderAtEnd(builder, state->exit);
 367 }
 368
 369
 370 /*
 371   Example of if/then/else building:
 372
 373      int x;
 374      if (cond) {
 375         x = 1 + 2;
 376      }
 377      else {
 378         x = 2 + 3;
 379      }
 380
 381   Is built with:
 382
 383      // x needs an alloca variable
 384      x = lp_build_alloca(builder, type, "x");
 385
 386
 387      lp_build_if(ctx, builder, cond);
 388         LLVMBuildStore(LLVMBuildAdd(1, 2), x);
 389      lp_build_else(ctx);
 390         LLVMBuildStore(LLVMBuildAdd(2, 3). x);
 391      lp_build_endif(ctx);
 392
 393  */
 394
 395
 396
 397 /**
 398  * Begin an if/else/endif construct.
 399  */
 400 void
 401 lp_build_if(struct lp_build_if_state *ifthen,
 402             struct gallivm_state *gallivm,
 403             LLVMValueRef condition)
 404 {
 405    LLVMBasicBlockRef block = LLVMGetInsertBlock(gallivm->builder);
 406
 407    memset(ifthen, 0, sizeof *ifthen);
 408    ifthen->gallivm = gallivm;
 409    ifthen->condition = condition;
 410    ifthen->entry_block = block;
 411
 412    /* create endif/merge basic block for the phi functions */
 413    ifthen->merge_block = lp_build_insert_new_block(gallivm, "endif-block");
 414
 415    /* create/insert true_block before merge_block */
 416    ifthen->true_block =
 417       LLVMInsertBasicBlockInContext(gallivm->context,
 418                                     ifthen->merge_block,
 419                                     "if-true-block");
 420
 421    /* successive code goes into the true block */
 422    LLVMPositionBuilderAtEnd(gallivm->builder, ifthen->true_block);
 423 }
 424
 425
 426 /**
 427  * Begin else-part of a conditional
 428  */
 429 void
 430 lp_build_else(struct lp_build_if_state *ifthen)
 431 {
 432    LLVMBuilderRef builder = ifthen->gallivm->builder;
 433
 434    /* Append an unconditional Br(anch) instruction on the true_block */
 435    LLVMBuildBr(builder, ifthen->merge_block);
 436
 437    /* create/insert false_block before the merge block */
 438    ifthen->false_block =
 439       LLVMInsertBasicBlockInContext(ifthen->gallivm->context,
 440                                     ifthen->merge_block,
 441                                     "if-false-block");
 442
 443    /* successive code goes into the else block */
 444    LLVMPositionBuilderAtEnd(builder, ifthen->false_block);
 445 }
 446
 447
 448 /**
 449  * End a conditional.
 450  */
 451 void
 452 lp_build_endif(struct lp_build_if_state *ifthen)
 453 {
 454    LLVMBuilderRef builder = ifthen->gallivm->builder;
 455
 456    /* Insert branch to the merge block from current block */
 457    LLVMBuildBr(builder, ifthen->merge_block);
 458
 459    /*
 460     * Now patch in the various branch instructions.
 461     */
 462
 463    /* Insert the conditional branch instruction at the end of entry_block */
 464    LLVMPositionBuilderAtEnd(builder, ifthen->entry_block);
 465    if (ifthen->false_block) {
 466       /* we have an else clause */
 467       LLVMBuildCondBr(builder, ifthen->condition,
 468                       ifthen->true_block, ifthen->false_block);
 469    }
 470    else {
 471       /* no else clause */
 472       LLVMBuildCondBr(builder, ifthen->condition,
 473                       ifthen->true_block, ifthen->merge_block);
 474    }
 475
 476    /* Resume building code at end of the ifthen->merge_block */
 477    LLVMPositionBuilderAtEnd(builder, ifthen->merge_block);
 478 }
 479
 480
 481 static LLVMBuilderRef
 482 create_builder_at_entry(struct gallivm_state *gallivm)
 483 {
 484    LLVMBuilderRef builder = gallivm->builder;
 485    LLVMBasicBlockRef current_block = LLVMGetInsertBlock(builder);
 486    LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
 487    LLVMBasicBlockRef first_block = LLVMGetEntryBasicBlock(function);
 488    LLVMValueRef first_instr = LLVMGetFirstInstruction(first_block);
 489    LLVMBuilderRef first_builder = LLVMCreateBuilderInContext(gallivm->context);
 490
 491    if (first_instr) {
 492       LLVMPositionBuilderBefore(first_builder, first_instr);
 493    } else {
 494       LLVMPositionBuilderAtEnd(first_builder, first_block);
 495    }
 496
 497    return first_builder;
 498 }
 499
 500
 501 /**
 502  * Allocate a scalar (or vector) variable.
 503  *
 504  * Although not strictly part of control flow, control flow has deep impact in
 505  * how variables should be allocated.
 506  *
 507  * The mem2reg optimization pass is the recommended way to dealing with mutable
 508  * variables, and SSA. It looks for allocas and if it can handle them, it
 509  * promotes them, but only looks for alloca instructions in the entry block of
 510  * the function. Being in the entry block guarantees that the alloca is only
 511  * executed once, which makes analysis simpler.
 512  *
 513  * See also:
 514  * - http://www.llvm.org/docs/tutorial/OCamlLangImpl7.html#memory
 515  */
 516 LLVMValueRef
 517 lp_build_alloca(struct gallivm_state *gallivm,
 518                 LLVMTypeRef type,
 519                 const char *name)
 520 {
 521    LLVMBuilderRef builder = gallivm->builder;
 522    LLVMBuilderRef first_builder = create_builder_at_entry(gallivm);
 523    LLVMValueRef res;
 524
 525    res = LLVMBuildAlloca(first_builder, type, name);
 526    LLVMBuildStore(builder, LLVMConstNull(type), res);
 527
 528    LLVMDisposeBuilder(first_builder);
 529
 530    return res;
 531 }
 532
 533
 534 /**
 535  * Like lp_build_alloca, but do not zero-initialize the variable.
 536  */
 537 LLVMValueRef
 538 lp_build_alloca_undef(struct gallivm_state *gallivm,
 539                       LLVMTypeRef type,
 540                       const char *name)
 541 {
 542    LLVMBuilderRef first_builder = create_builder_at_entry(gallivm);
 543    LLVMValueRef res;
 544
 545    res = LLVMBuildAlloca(first_builder, type, name);
 546
 547    LLVMDisposeBuilder(first_builder);
 548
 549    return res;
 550 }
 551
 552
 553 /**
 554  * Allocate an array of scalars/vectors.
 555  *
 556  * mem2reg pass is not capable of promoting structs or arrays to registers, but
 557  * we still put it in the first block anyway as failure to put allocas in the
 558  * first block may prevent the X86 backend from successfully align the stack as
 559  * required.
 560  *
 561  * Also the scalarrepl pass is supposedly more powerful and can promote
 562  * arrays in many cases.
 563  *
 564  * See also:
 565  * - http://www.llvm.org/docs/tutorial/OCamlLangImpl7.html#memory
 566  */
 567 LLVMValueRef
 568 lp_build_array_alloca(struct gallivm_state *gallivm,
 569                       LLVMTypeRef type,
 570                       LLVMValueRef count,
 571                       const char *name)
 572 {
 573    LLVMBuilderRef first_builder = create_builder_at_entry(gallivm);
 574    LLVMValueRef res;
 575
 576    res = LLVMBuildArrayAlloca(first_builder, type, count, name);
 577
 578    LLVMDisposeBuilder(first_builder);
 579
 580    return res;
 581 }